// detalii algoritm: http://infoarena.ro/flux-si-cuplaj
// evaluator:        http://infoarena.ro/problema/maxflow
#include<fstream>
#define oo 0x3f3f3f3f
using namespace std;
int v[1000][1000],a[1000][1000],n,m,viz[100],xx,yy;
//xx - nodul sursa
//yy - nodul destinatie
//n - numatul de noduri
//m - numarul de muchii
//v=matricea de capacitate
//a=maticea de flux
void citire()
{
	int i,j,k,qwe;
	ifstream in("maxflow.in");
	in>>n>>m;
	xx=1;
	yy=n;
	for (k=1;k<=m;k++)
	{
		in>>i>>j>>qwe;
		v[i][j]+=qwe;
	}
	in.close();
}
int bf()
{
	int x,i,st[10000],pi,ps;
	memset(viz,0,sizeof(viz));
	pi=ps=1;
	st[pi]=xx;
	while (pi<=ps)
	{
		x=st[pi];
		for (i=1;i<=n;i++)
		{
			if (v[x][i]-a[x][i]>0&&!viz[i])
			{
				viz[i]=x;			
				st[++ps]=i;
			}
		}
		pi++;
	}
	if (viz[yy])
		return 1;
	return 0;
}
int ff()
{
	int flux=0,i,mn;
	while (bf())
	{
		mn=oo;
		for (i=yy;i!=xx;i=viz[i])
			if (v[viz[i]][i]-a[viz[i]][i]<mn)
				mn=v[viz[i]][i]-a[viz[i]][i];
		for (i=yy;i!=xx;i=viz[i])
		{
			a[viz[i]][i]+=mn;
			a[i][viz[i]]-=mn;
		}
		flux+=mn;
	}
	return flux;
	
}


	
int main()
{
	citire();
	ofstream out("maxflow.out");
	out<<ff()<<'\n';
	
	
}