#include <fstream>
#define nmax 1005
#define INF 1 << 20

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;
	lista * p;
	for(int i = 1; i <= n; ++ i)
		uz[i] = 0;
	uz[1] = 1;
	cs[1] = 1;
	st = dr = 1;
	while(st <= dr)
	{
		int nod = cs[st];
		for(p = g[nod]; p; 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;
	lista * p;
	for(; bfs(); )
	{
		for(p = g[n]; p; p = p->nod)
		{
			nod = p->inf;
			// if(nod == n) continue;
			t[n] = nod;

			if(f[nod][n] == c[nod][n] || !uz[nod]) continue;
			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;
			ff += flux;
			// fout << ff << "\n";

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