/*
ID: c_iulya1
LANG: C++
TASK: ditch
*/

#include<cstdio>
#include<algorithm>
using namespace std;
long c[1001][1001],n,m,gata,v[1001],a[1001][1001],cd[1000001],d[1000001];
long R,F,r[1000001];

void rd()
{
scanf("%ld%ld",&n,&m);
for(int i=1;i<=m;i++)
	{
	long x,y,z;
	scanf("%ld%ld%ld",&x,&y,&z);
	a[x][++a[x][0]]=y;
	c[x][y]=z;
	
	a[y][++a[y][0]]=x;
	}
}

void bf(int i)
{
long st=1,dr=2;
cd[1]=i;
v[i]=1;

while(st<dr)
	{
	int u=cd[st];
		
	for(int j=1;j<=a[u][0];j++)
		if(c[u][a[u][j]]&&!v[a[u][j]])
			{
			v[a[u][j]]=1;
			cd[dr]=a[u][j];
			d[dr]=st;
			
			if(r[u]==0)
				r[dr]=c[u][a[u][j]];
			else 
				r[dr]=min(r[u],c[u][a[u][j]]);
			
			if(a[u][j]==n)
				{
				R=r[dr];
				gata=0;
				
				for(int k=dr;d[k];k=d[k])
					{
					c[cd[d[k]]][cd[k]]-=R;
					c[cd[k]][cd[d[k]]]+=R;					
					}
				
				return;
				}		
			dr++;
			}
	st++;
	}
}

void go()
{
while(!gata)
	{
	for(int k=1;k<=n;k++)
		v[k]=r[k]=cd[k]=d[k]=0;
	gata=1;
	R=10000010;
	bf(1);
	if(!gata) 
		F+=R;
	}
	
printf("%ld\n",F);
}

int main()
{
freopen("maxflow.in","r",stdin);
freopen("maxflow.out","w",stdout);

rd();
go();

return 0;
}