#include <fstream>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#ifdef __ACASA__
#define MAXN 11
#else
#define MAXN 1001
#endif

int C[MAXN][MAXN];
int F[MAXN][MAXN];
int T[MAXN];
int N, M, flux, r, i;

int BF() {
	queue<int> Q;
	Q.push(1);
	T[1] = -1;
	memset( T, 0, sizeof(T) );
	while ( !Q.empty() ) {
		int x = Q.front();
		for ( int i=1; i<=N; ++i ) 
			if ( C[x][i]>F[x][i] && T[i]==0 ) {
				Q.push(i); T[i] = x; 
			}
		Q.pop();
	}
	return T[N] != 0;
}

int main() {
	// load
	ifstream in("maxflow.in");
	in >> N >> M;
	while ( M-- ) {
		int x, y, c;
		in >> x >> y >> c;
		C[x][y] = c;
	}

	//flow
	while ( BF() )
		for ( int j=1; j<N; ++j ) 
			if ( C[j][N] > F[j][N] ) {
				r = C[j][N] - F[j][N];
				for ( i=j; i!=1; i=T[i] )
					r = r>(C[T[i]][i]-F[T[i]][i]) ? C[T[i]][i]-F[T[i]][i] : r;
				for ( i=j; i!=1; i=T[i] ) 
					F[T[i]][i] += r, F[i][T[i]] -= r;
				F[j][N] += r, F[N][j] -= r;
				flux += r;
			}


	// output
	ofstream("maxflow.out") << flux << "\n";
	return 0;
}