#include <fstream>
#include <queue>

#define NMAX 1001
using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");


int N,M,S,T,C[NMAX][NMAX], GR[NMAX][NMAX] , F[NMAX][NMAX];
int pred[NMAX], viz[NMAX];



bool bfs()
{
	for ( int i = 1; i <= N; i++ )
		viz[i] = pred[i] = 0;
	queue<int> Q;
	Q.push(S);
	viz[S] = 1;
	while ( !Q.empty() )
	{
		int nod = Q.front(); Q.pop();
		for ( int i = 1; i <= N; i++ )
		{
			if ( GR[nod][i] && !viz[i] )
			{
				viz[i] = 1;
				pred[i] = nod;
				Q.push(i);
				if ( i == T )
					return true;
			}
		}
	}
	return false;
}


int main()
{
	f >> N;
	//f >> S >> T;
	S = 1;
	T = N;
	f >> M;
	for ( int i = 0; i < M; i++ )
	{
		int x, y;
		f >> x >> y >> C[x][y];
		F[x][y] = 0;/// >> F[x][y];
		GR[x][y] = C[x][y] - F[x][y];
		GR[y][x] = F[x][y];
	}

	while( bfs() )
	{
		int amin = 100000;
		int x = T;
		while ( pred[x] )
		{
			if ( amin > GR[pred[x]][x] ) amin = GR[pred[x]][x];
			x = pred[x];
			if ( x == S ) break;
		}

		x = T;
		while ( pred[x] )
		{
			if ( C[ pred[x]][x]  )
			{
				F[pred[x]][x] += amin;
				GR[pred[x]][x] -= amin;
				GR[x][pred[x]] += amin;
			}
			else
			{
				F[x][pred[x]] -= amin;
				GR[x][pred[x]] += amin; 
				GR[pred[x]][x] -= amin;
			}
			x = pred[x];
			if ( x == S ) break;
		}
	}
	int flux = 0;
	for ( int i = 1; i <= N; i++ )
	{
		flux += F[S][i];
	}
	g << flux;
}