#include <bits/stdc++.h>
using namespace std;
const int PART = 1000;
const int CAND = 1000;
const int MAXN = PART + CAND + 1;

ifstream fin( "maxflow.in" );
ofstream fout( "maxflow.out" );

struct MAX_FLOW{
  int source, dest;
  int cap[MAXN+1][MAXN+1];
  int flow[MAXN+1][MAXN+1];
  vector <int> edges[MAXN+1];
  int parent[MAXN+1];
  void addEdge( int a, int b, int capacity ) {
    edges[a].push_back( b );
    edges[b].push_back( a );
    cap[a][b] = capacity;
    cap[b][a] = 0;
  }
  void changeEdge( int a, int b, int new_cap ) {
    cap[a][b] = new_cap;
    cap[b][a] = 0;
  }
  void bfs( int node ) {
    int i;
    for( i = 0; i <= dest; i++ )
      parent[i] = -1;
    parent[source] = -2;
    queue <int> q;
    q.push( source );
    while( !q.empty() ) {
      auto qfront = q.front();
      q.pop();
      if( qfront == dest )
        return;
      for( auto vec: edges[qfront] ) {
        if( parent[vec] == -1 && cap[qfront][vec] - flow[qfront][vec] > 0 ) {
          parent[vec] = qfront;
          q.push( vec );
        }
      }
    }
  }
  int flux() {
    int node, new_flow, totalFlow, i, j;
    for( i = 0; i <= dest; i++ ) {
      for( j = 0; j <= dest; j++ )
        flow[i][j] = 0;
    }
    totalFlow = 0;
    bfs( source );
    while( parent[dest] != -1 ) {
      for( auto vec: edges[dest] ) {
        if( parent[vec] != -1 ) {
          parent[dest] = vec;
          node = dest;
          new_flow = 1e9;
          while( node != source ) {
            new_flow = min( new_flow, cap[parent[node]][node] - flow[parent[node]][node] );
            node = parent[node];
          }
          node = dest;
          while( node != source ) {
            flow[parent[node]][node] += new_flow;
            flow[node][parent[node]] -= new_flow;
            node = parent[node];
          }
          totalFlow += new_flow;
        }
      }
      bfs( source );
    }
    return totalFlow;
  }
};

MAX_FLOW votes;

int frecv[PART+1][CAND+1];
int main() {
  /*
  int n, k, i, nr, x, ones, j, st, dr, mij;
  fin >> n >> k;
  ones = 0;
  for( i = 1; i <= n; i++ ) {
    fin >> nr;
    for( j = 0; j < nr; j++ ) {
      fin >> x;
      if( j != 0 )
        frecv[i][x]++;
    }
    if( frecv[i][1] == 0 )  // inseamna ca nu pot sa-l pun primul
      i--, n--, ones++;
  }
  votes.source = 0;
  votes.dest = n + k + 1;
  for( i = 1; i <= n; i++ )
    votes.addEdge( votes.source, i, 1 );
  for( i = n + 1; i <= n + k; i++ )
    votes.addEdge( i, votes.dest, 1 );
  for( i = 1; i <= n; i++ ) {
    for( j = 1; j <= k; j++ ) {
      if( frecv[i][j] == 0 )
        votes.addEdge( i, n + j, 1 );
    }
  }
  st = -1;
  dr = n;
  while( dr - st > 1 ) {
    mij = ( st + dr ) / 2;
    for( i = n + 1; i <= n + k; i++ ) {
      votes.changeEdge( i, votes.dest, mij );
    }
    x = votes.flux();
    if( x == n )
      dr = mij;
    else
      st = mij;
  }
  fout << max( 0, dr + 1 - ones );*/
  int n, m, a, b, c, i;
  fin >> n >> m;
  votes.source = 1;
  votes.dest = n;
  for( i = 0; i < m; i++ ) {
    fin >> a >> b >> c;
    votes.addEdge( a, b, c );
  }
  fout << votes.flux();
  return 0;
}