#include<fstream>
using namespace std;
#define N 1002
#define inf 1000000000
int cap[N][N],flux[N][N];
int n,m,x,y,c,i;
int Q[N],viz[N],t[N],cn[N];
int bfs(int s,int d)
{int i,p,u,nd;
  p=u=1; Q[1]=s;
  for(i=1;i<=n;i++)t[i]=0;
  t[s]=1;
	while(p<=u)
	{
		nd=Q[p++];
		for(i=1;i<=n;i++)
		  if(!t[i])
		  if(cap[nd][i]>flux[nd][i])
		  {
			t[i]=nd;
			Q[++u]=i;
		  }
	}
	return t[d];
}
int dinic(int s,int d)
{int flow=0,minn,i,j;
	while(bfs(s,d))
	{
	  for(j=1;j<=cn[0];j++)
	   if(cap[cn[j]][d]>flux[cn[j]][d])
	   {
		minn=cap[cn[j]][d]-flux[cn[j]][d];
		 for(i=cn[j];i!=s;i=t[i])
			minn=min(minn,cap[t[i]][i]-flux[t[i]][i]);
		 
		  flux[cn[j]][d]+=minn;
		  flux[d][cn[j]]-=minn;
		 for(i=cn[j];i!=s;i=t[i])
		 {
		  flux[t[i]][i]+=minn;
		  flux[i][t[i]]-=minn;
		 }
		 flow+=minn;
	   }
	}
	return flow;
}
int main()
{
	ifstream f("maxflow.in");ofstream g("maxflow.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		cap[x][y]=c;
	}
	for(i=1;i<=n;i++)if(cap[i][n])cn[++cn[0]]=i;//tin minte vecinii lui n
	g<<dinic(1,n);
	f.close();g.close();
return 0;}