#include<fstream>
#include<queue>
#define dmax 1005
#define inf 32000
using namespace std;

queue<int> q;
long n,m,s,d;
long c[dmax][dmax],f[dmax][dmax];
int viz[dmax],lant[dmax];
long llant,a,b,flux;


int bfs()
{
 long i,elem;
	
 for (i=1; i<=n; i++)
	 viz[i]=0;
 
 q.push(s);
 while (q.size() && viz[d] == 0)
	 {
	  elem=q.front();
	  for (i=1; i<=n; i++)
		  if (viz[i]==0)
			  if (f[elem][i] < c[elem][i])
				  {
				   viz[i]=elem;
				   q.push(i);
				  } else
				  if (f[i][elem] > 0)
					  {
					   viz[i]=-elem;
					   q.push(i);
					  }
	  q.pop();
	 }
 
 while (q.size())
	 q.pop();
 
 return viz[d];
}

void EK()
{
 long i,v;
	
 if (bfs()==0)
	 return; else
	 {
	  lant[1]=d; llant=1; a=b=inf;
	  while (lant[llant] != s)
		  {
		   llant++;
		   lant[llant]=abs(viz[lant[llant-1]]);
		   
		   if (viz[lant[llant-1]] > 0)
			   a=min(a, c[lant[llant]][lant[llant-1]] - f[lant[llant]][lant[llant-1]]); else
			   b=min(b, f[lant[llant-1]][lant[llant]]);
		  }
	  v=min(a,b);
	  for (i=llant; i>1; i--)
		 if (viz[lant[i-1]] > 0)
		     f[lant[i]][lant[i-1]]+=v; else
			 f[lant[i-1]][lant[i]]-=v;
			
	  EK();
	 }
}

int main()
{
 long i,x,y,z;
	
 ifstream fin("maxflow.in");
 fin>>n>>m;
 for (i=1; i<=m; i++)
	 {
	  fin>>x>>y>>z;
	  c[x][y]=z;
	 }
 s=1; d=n;
 
 EK();
 ofstream fout("maxflow.out");
 for (i=1; i<=n; i++)
	 flux+=f[i][d];
 fout<<flux;
 
 fin.close();
 fout.close();
 
 return 0;
}