#include<stdio.h>
#define Nmax 1024

int n,m;
long c[Nmax][Nmax],f[Nmax][Nmax],viz[Nmax],q[Nmax];

long minim(long a,long b)
{	return (a<b)?a:b;	}

long abs(long x)
{	return (x>0)?x:-x;	}

void citire();
void rez();
void afisare();
int bf();

int main()
{	
	citire();
	rez();
	afisare();
	return 0;
}

void citire()
{	int i,x,y;long z;
	freopen("maxflow.in","r",stdin);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{	scanf("%d %d %ld",&x,&y,&z);
		c[x][y]=z;
	}
}

void rez()
{	int i,lg;
	long a,b,v;
	int L[Nmax];
	do
	{	for (i=1;i<=n;i++) viz[i]=0;
		if (bf()) return;
		L[0]=n;lg=0;
		a=b=2000000000;
		while (L[lg]!=1)
		{	++lg;
			L[lg]=abs(viz[L[lg-1]]);
			if (viz[L[lg-1]]>0)
				a=minim(a,c[L[lg]][L[lg-1]]-f[L[lg]][L[lg-1]]);
			else
				if (viz[L[lg-1]]<0)
					b=minim(b,f[L[lg-1]][L[lg]]);
		}
		v=minim(a,b);
		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 bf()
{	int b,v,i,x;
	q[0]=1;b=v=0;viz[1]=1;
	while (b<=v&&!viz[n])
	{	x=q[b++];
		for (i=1;i<=n;i++)
			if (!viz[i])
				if (f[x][i]<c[x][i])
				{	viz[i]=x;q[++v]=i; }
				else
					if (f[i][x]>0)
					{	viz[i]=-x;q[++v]=i; }
	}
	return !viz[n];
}

void afisare()
{	long flux=0;int i;
	for (i=1;i<=n;i++) flux+=f[i][n];
	freopen("maxflow.out","w",stdout);
	printf("%ld\n",flux);
}