#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

#define INPUT "maxflow.in"
#define OUTPUT "maxflow.out"
#define CL(X) memset(X, 0, sizeof(X))

const int NMAX = 1001;
const long INFI = 2000000000;

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

int N, M;
long Cap[ NMAX ][ NMAX ], Flow[ NMAX ][ NMAX ];
int Father[ NMAX ], vis[ NMAX ], bf[ NMAX ];

void readData()
{
  int Node1, Node2;
  long Cost;

  fscanf(fin, "%d %d", &N, &M);

  for(int i = 0; i < M; ++i)
  {
    fscanf(fin, "%d %d %ld", &Node1, &Node2, &Cost);

    Cap[ Node1 ][ Node2 ] = Cost;
    Cap[ Node2 ][ Node1 ] = -Cost;
  }
}

int BFS()
{
  CL( vis ); CL( bf );

  vis[ 1 ] = 1;
  bf[ 1 ] = 1;
  Father[ 1 ] = -1;
  long Poz = 1;
  long Cont = 1;
  int ok = 0;

  while(Poz <= Cont)
  {
    ok = 0;
    for(int i = 1; i <= N; ++i)
      if(Cap[ bf[ Poz ] ][ i ] - Flow[ bf[ Poz ] ][ i ] > 0 && !vis[ i ])
        bf[ ++Cont ] = i, vis[ i ] = 1, Father[ i ] = bf[ Poz ];
    ++Poz;;
  }

  return vis[ N ];
}

void solve()
{
  long minim;

  while( BFS() )
  {
    minim = INFI;

    for(int i = N; Father[ i ] != -1; i = Father[ i ])
      if(minim > Cap[ Father[ i ] ][ i ] - Flow[ Father[ i ] ][ i ]) minim = Cap[ Father[ i ] ][ i ] - Flow[ Father[ i ] ][ i ];

    for(int i = N; Father[ i ] != -1; i = Father[ i ])
    {
      Flow[ Father[ i ] ][ i ] += minim;
      Flow[ i ][ Father[ i ] ] = -Flow[ Father[ i ] ][ i ];
    }

  }

  long Sum = 0;

  for(int i = 1; i <= N; ++i)
    if(Flow[ i ][ N ] > 0 ) Sum += Flow[ i ][ N ];

  fprintf(fout, "%ld\n", Sum);
}

int main()
{
  readData();

  solve();

  fclose(fin);
  fclose(fout);

  return 0;
}