#include <queue>
#include <vector>
#include <fstream>
#define inf 0x3f3f3f3f

/*
 *
 */
using namespace std;
struct pr
{
	int f, w, c;
	pr( void ) : f(-1), w(0), c(inf) {};
	pr( int _f, int _w, int _c ) : f(_f), w(_w), c(_c) { };
	inline bool operator<( const pr& x ) const
	{
		return x.c > c;
	}
};
int N;
int C[ 1000 ][ 1000 ];
int find_path( void )
{
	int min_c, i;
	vector< int > father( N+1, -1 );
	priority_queue< pr, vector< pr > > PQ;
	PQ.push( pr() );
	while( !PQ.empty() )
	{
		pr x=PQ.top(); PQ.pop();
		father[x.w]=x.f;
		if( N == x.w )
		{
			min_c=x.c;
			break;
		}
		for( i=0; i <= N; ++i )
			if( C[x.w][i] > 0 )
				PQ.push( pr( x.w, i, min( x.c, C[x.w][i] ) ) );
	}
	if( -1 == father[N]  )
		return -1;
	father[0]=-1;
	for( i=N; -1 != father[i]; i=father[i] )
	{
		C[ father[i] ][ i ]-=min_c;
		C[ i ][ father[i] ]+=min_c;
	}
	return min_c;	
}
inline int Maximum_Flow( void )
{
	int path_c, s=0;
	for( path_c=find_path(); -1 != path_c; s+=path_c, path_c=find_path() );
	return s;
}
int main( void )
{
	int M, x, y;
	ifstream in( "maxflow.in" );
	in>>N>>M;
	N-=1;
	for( ; M; --M )
		in>>x>>y, in>>C[x-1][y-1];
	ofstream out( "maxflow.out" );
	out<<Maximum_Flow();
	return 0;
}