#include <fstream>
#include <cstring>
#define INF 1 << 15
#define nmax 1005

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int n, m, flux, fmin;
int c[nmax][nmax], f[nmax][nmax], q[nmax], t[nmax];

struct lista
{
	int inf;
	lista * nod;
} * g[nmax];

inline int minim(int a, int b)
{
	if(a < b)
		return a;
	return b;
}

void add(int i, int j)
{
	lista * p;
	p = new lista;
	p -> inf = j;
	p -> nod = g[i];
	g[i] = p;
}

int bfs()
{
	memset(t, 0, sizeof(t));
	lista * p;
	int st, dr, nod;
	st = dr = 1;
	q[st] = 1;
	t[st] = -1;
	while(st <= dr)
	{
		nod = q[st];
		for(p = g[nod]; p; p = p->nod)
			if(!t[p->inf] && c[nod][p->inf] > f[nod][p->inf])
			{
				t[p->inf] = nod;
				q[++ dr] = p->inf;
				if(p->inf == n) return 1;
			}
		++ st;
	}
	return 0;
}

int main()
{
	int i, j, nod, a, b, cost, nr = 0;
	fin >> n >> m;
	for(i = 1; i <= m; ++ i)
	{
		fin >> a >> b >> cost;
		c[a][b] += cost;
		add(a, b);
		// add(b, a);
	}
	for(flux = 0; bfs(); )
		for(i = 1; i <= n; ++ i)
		{
			if(t[i] == -1 || c[i][n] <= f[i][n])
				continue;
			fmin = c[i][n] - f[i][n];
			for(nod = i; nod != 1; nod = t[nod])
				fmin = minim(fmin, c[ t[nod] ][nod] - f[ t[nod] ][nod]);
			if(fmin == 0) continue;
			f[i][n] += fmin;
			f[n][i] -= fmin;
			for(nod = i; nod != 1; nod = t[nod])
			{
				f[ t[nod] ][nod] += fmin;
				f[nod][ t[nod] ] -= fmin;
			}
			flux += fmin;
		}
	fout << flux << "\n";
	return 0;
}