#include<cstdio>
#define nrmax 1003
#define min(x,y) ((x<y)?(x):(y))
#define mod(x) (((x)>0)?(x):(-x))
int n,m,x,y,z,i,c[nrmax][nrmax],f[nrmax][nrmax],viz[nrmax],q[nrmax];
void citire()
{
	freopen("maxflow.in","r",stdin);
	freopen("maxflow.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		c[x][y]=z;
	}
}
int marcaj()
{
	int p,u,i,x;
	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,lg,v,l[nrmax];
	do
	{
		for(i=1;i<=n;i++)
			viz[i]=0;
		if(marcaj())return;
		l[0]=n;
		lg=0;
		a=b=10000;
		while(l[lg]!=1)
		{
			++lg;
			l[lg]=mod(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);
		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);
}
void afisare()
{
	int i,vf=0;
	for(i=1;i<=n;i++)
		vf+=f[i][n];
	printf("%d", vf);
}
int main()
{
	citire();
	ek();
	afisare();
}