#include<fstream>
using namespace std;
int cap[1001][1001],flux[1001][1001],l[1001];//l=land de la destinatie la sursa
int n,m,x,y,c,i;
short viz[1002];
ofstream g("maxflux.out");
int abs(int nr)
{
	if(nr>-1)return nr;
	return -nr;
}
int minim(int a,int b)
{
	if(a<b)return a;
	return b;
}
int bfs(int s)
{int u=1,p=1,nd=1,i,c[1001];//nodul sursa = 1
  c[1]=1; //viz[1]=s;
	while(p<=u)
	{
		for(i=1;i<=n;i++)
		{
		  if(cap[nd][i] && !viz[i])//daca am muchie de la nd la i
			if(cap[nd][i]>flux[nd][i])
			{ 
				c[++u]=i; viz[i]=nd;
			}
			/*else
			if(cap[nd][i])
			{
				c[++u]=i; viz[i]=-nd;//avem arc saturat
			}*/
		}
	  nd=c[++p];
	}
   return viz[n];//daca nu e vizitat fluxul este maxim
}

void ek(int s,int d)
{int a=110001,k,fluxmax=0;//maresc fluxul cu minimul lui a
	while(bfs(s))
	{
		k=0; l[k]=d;
		while(l[k]!=s)
		{
			k++;
			l[k]=abs(viz[l[k-1]]);//introdul in land nodul care intra in nodul curent
			if(cap[l[k]][l[k-1]]>flux[l[k]][l[k-1]]) 
				a=minim(a,cap[l[k]][l[k-1]]-flux[l[k]][l[k-1]]);//minimul de marire de flux
		}
		for(k;k>0;k--)
			flux[l[k]][l[k-1]]+=a;
		for(i=1;i<=n;i++)viz[i]=0;
	}
	for(i=1;i<=n;i++) fluxmax+=flux[i][n];
	g<<fluxmax;
}

int main()
{
	ifstream f("maxflux.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		cap[x][y]=c;
	}
	ek(1,n);//edmonds-karp
	f.close();g.close();
return 0;}