#include<stdio.h>
#include<stdlib.h>

int c[1001][1001],f[1001][1001],n,m,viz[1001];
FILE *ff;

void read ()
{
	ff=fopen("maxflow.in","r");
	fscanf(ff,"%d%d",&n,&m);
	int i,x,cap,y;
	for (i=1;i<=m;++i)
	{
		fscanf(ff,"%d%d%d",&x,&y,&cap);
		c[x][y]=cap;
	}
	fclose(ff);
}

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

int bfs ()
{
	//returneaza 1 daca iesirea nu a fost marcata
	int x,p,u,q[1001],i;
	q[0]=1;
	p=u=0;
	viz[1]=1;
	while (p<=u && !viz[n])
	{
		x=q[p++];
		for (i=1;i<=n;++i)
			if (!viz[i])
				if (f[x][i]<c[x][i])
				{
					viz[i]=x;
					q[++u]=i;
				}
				else
					if (f[i][x]>0)
					{
						viz[i]=-x;
						q[++u]=i;
					}
	}
	return !viz[n];
}

void ek ()
{
	int i,a,b,l[1001],lg,v;
	do {  //marcam varfurile prin bfs
		for (i=1;i<=n;++i)
			viz[i]=0;
		if ( bfs() )
			return;
		//determin lantul de ameliorare
		l[0]=n;
		lg=0;
		a=b=100000;
		while (l[lg]!=1)
		{
			++lg;
			l[lg]=abs(viz[l[lg-1]]);
			if (viz[l[lg-1]] > 0)
				a=min(a,c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]);
			else
				if (viz[l[lg-1]] < 0)
					b=min(b,f[l[lg-1]][l[lg]]);
		}
	v=min(a,b);
	//marim fluxul de-alungul lantului
	for (i=lg;i>0;--i)
		if (viz[l[i-1]]>0)
			f[l[i]][l[i-1]]+=v;
		else
			f[l[i-1]][l[i]]-=v;
	} while (1);
}

int main ()
{
	read ();
	ek ();
	int i,max,vf=0;
	ff=fopen("maxflow.out","w");
	for (i=1;i<=n;++i)
		vf+=f[i][n];
	fprintf(ff,"%d",vf);
	fclose(ff);
	return 0;
}