#include <iostream>
#include <queue>
#include <vector>
#include <deque>
using namespace std;
long long g[200][200];
long long f[200][200];
int main(){
  while(1){
    int n, m;
    cin >> n >> m;
    if(!cin)break;
    for(int i=0;i<m;i++){
      for(int j=0;j<m;j++){
        g[i][j] = 0;
        f[i][j] = 0;
      }
    }
    for(int i=0;i<n;i++){
      long long a,b,c;
      cin >> a >> b >> c;
   // g[a-1][b-1] = c;          <- wrong orz
      g[a-1][b-1] += c;
    }
    while(1){
      vector<int> prev(m);
      deque<int> path;
      for(int i=0;i<m;i++){
        prev[i] = -1;
      }
      queue<int> q;
      q.push(0);
      while(!q.empty()){
        int current = q.front();
        q.pop();
        if(current == m-1){
          while(1){
            path.push_front(current);
            if(current == 0)break;
            current = prev[current];
          }
          break;
        }
        for(int i=0;i<m;i++){
          if(prev[i] == -1 && g[current][i] - f[current][i] > 0){
            q.push(i);
            prev[i] = current;
          }
        }
      }
      if(path.size() == 0)break;
      long long mincost = 1<<30;
      for(int i=0;i<path.size()-1;i++){
        int u = path[i];
        int v = path[i+1];
        if(g[u][v]-f[u][v] < mincost)mincost = g[u][v]-f[u][v];
      }
      for(int i=0;i<path.size()-1;i++){
        int u = path[i];
        int v = path[i+1];
        f[u][v] += mincost;
        f[v][u] -= mincost;
      }
    }
    long long result = 0;
    for(int i=0;i<m;i++){
      result += f[0][i];
    }
    cout << result << endl;
  }
  return 0;
}