#include <iostream.h>
#include <fstream.h>
#include <math.h>

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");


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




int bf()
{int i,p,u;
int q[1000];
 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;
 }




int main()
{int min, i,j, cc,m;
 fin>>n>>m;
 s=1;d=n;

 while(fin>>i>>j>>cc)
  c[i][j]+=cc;

while (bf())
{i=d; min=200000;

 for (j=1;j<=n;j++)
 { if (t[j]>0 && c[t[j]][j]>f[t[j]][j])
    min=c[t[j]][j]-f[t[j]][j];


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

  flux+=min;

  i=d;

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

fout<<flux;
fout.close();
return 0;
}