#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) { };
} H[ 1024 ];
int N, N2;
int C[ 1000 ][ 1000 ];
void DownHeap( int k )
{
	int son;
	while( true )
	{
		son=2*k;
		if( son > N2 )
			return;
		if( son < N2 && H[son].c < H[son+1].c )
			++son;
		if( H[k].c >= H[son].c )
			return;
		swap( H[k], H[son] );
		k=son;
	}
}
void UpHeap( int k )
{
	int key=H[k].c, f=k/2;
	while( k > 1 && key > H[f].c )
	{
		swap( H[k], H[f] );
		k=f;
		f/=2;
	}
}
inline void push( const pr& x )
{
	H[++N2]=x;
	UpHeap( N2 );
}
inline pr pop( void )
{
	pr r=H[1];
	H[1]=H[N2--];
	DownHeap( 1 );
	return r;
}
int find_path( void )
{
	N2=0;
	int min_c=0, i;
	vector< int > father( N+1, -1 );
	push( pr() );
	while( N2 )
	{
		pr x=pop();
		father[x.w]=x.f;
		if( N == x.w )
		{
			min_c=x.c;
			break;
		}
		for( i=1; i <= N; ++i )
			if( C[x.w][i] > 0 )
				push( pr( x.w, i, min( x.w, C[x.w][i] ) ) );
	}
	if( -1 == father[N] )
		return 0;
	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(); 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;
}