#include <fstream>
#include <cstring>
#define nmax 1005
#define INF 999999

using namespace std;

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

int ff, flux;
int n, m;
int uz[nmax], c[nmax][nmax], cs[nmax], f[nmax][nmax], t[nmax];

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

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

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

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

int main()
{
	int i;
	int a, b, cost;
	fin >> n >> m;
	for(i = 1; i <= n; ++ i)
	{
		fin >> a >> b >> cost;
		c[a][b] = cost;
		add(a, b);
		add(b, a);
	}
	int nod, poz = 0;
	lista * p;
	for(; bfs(); )
	{
		for(p = g[n]; p; p = p->nod)
		{
			nod = p->inf;
			// if(nod == n) continue;

			if(f[nod][n] == c[nod][n] || !uz[nod])
				continue;
			t[n] = nod;
			flux = INF;

			for(nod = n; t[nod] != 1; nod = t[nod])
				flux = minim(flux, c[ t[nod] ][nod] - f[ t[nod]][nod] );

			if(flux == 0)
				continue;

			for(nod = n; t[nod] != 1; nod = t[nod])
			{
				f[ t[nod] ][nod] += flux;
				f[ nod][ t[nod]]  -= flux;
			}
			ff += flux;
			// fout << ff << " " << poz << "\n";
		}
	}
	fout << ff << "\n";
	return 0;
}