#include <stdio.h>
#include <iostream.h>

#define IN "maxflow.in"
#define OUT "maxflow.out"
#define MAX 1002

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

int t[MAX];
int n,s,d;
long flux;
long c[MAX][MAX],f[MAX][MAX];

int bf();

int main()
{
 long min,cc;
 int i,j,m;
 int x,y;

 fscanf(fin,"%d %d",&n,&m);
 s=1;
 d=n;

 for(i=1;i<=m;i++)
 {
  fscanf(fin,"%d %d %ld",&x,&y,&cc);
  c[x][y]+=cc;
 }
 fclose(fin);
  
 while( bf() )
  for(j=1;j<=n;j++)
  {
   if(t[j]>0 && c[j][n]>f[j][n])
    min=c[j][n]-f[j][n];
   else
    continue;

   i=j;
   
   while(i!=s && min)
   {
    if(min>c[t[i]][i]-f[t[i]][i])
     min=c[t[i]][i]-f[t[i]][i];
    i=t[i];
   }

   if(min==0)
    continue;

   f[j][n]+=min;
   f[n][j]-=min;

   flux+=min;
   i=j;

  while(i!=s)
  {
   f[t[i]][i]+=min;
   f[i][t[i]]-=min;
   i=t[i];
  }
 }

 fprintf(fout,"%ld\n",flux);
 
 fclose(fout);
return 0;
}

int bf()
{
 int i,p,u;
 int q[MAX];
 
 memset(t,0,sizeof(t));

 p=u=1;
 q[p]=s;
 t[s]=-1;

 for(;p<=u;p++)
  for(i=1;i<=n;i++)
   if(!t[i] && c[q[p]][i]>f[q[p]][i])
   {
    u++;
    q[u]=i;
    t[i]=q[p];
    
    if(i==d)
     return 1;
   }
   
 return 0;
}