#include <stdio.h>
#include <vector>
using namespace std;
#define NMAX 1001
vector<int> l[NMAX],lt[NMAX];
#define abs(x) ((x>0)?(x):(-(x)))
long c[NMAX][NMAX],f[NMAX][NMAX];
int n,C[NMAX],k,viz[NMAX];
void read()
 {
 int m,x,y,cost;
 FILE *f=fopen("maxflow.in","r");
 fscanf(f,"%d %d",&n,&m);
 for(int i=1;i<=m;i++)
  {
  fscanf(f,"%d %d %d",&x,&y,&cost);
  c[x][y]=cost;
  l[x].push_back(y);
  lt[y].push_back(x);
  }
 fclose(f);
 }
int bfs()
 {
 int j,i,x,y;
 for(i=1;i<=n;i++) viz[i]=0;
 k=0;
 C[++k]=1;
 viz[1]=1;
 for(i=1;i<=k&&!viz[n];i++)
  {
  x=C[i];
  for(j=0;j<l[x].size()&&!viz[n];j++)
   {
   y=l[x][j];
   if(!viz[y]&&c[x][y]>f[x][y])
    {
    C[++k]=y;
    viz[y]=x;
    }
   }
  for(j=0;j<lt[x].size();j++)
   {
   y=lt[x][j];
   if(f[y][x]>0&&!viz[y])
    {
    C[++k]=y;
    viz[y]=-x;
    }
   }
  }
 return viz[n];
 }
void solve()
 {
 int bk[NMAX],o,mn,i;
 while(bfs())
  {
  mn=110001;
  o=0;
  bk[++o]=n;
  while(bk[o]!=1)
   {
   bk[o+1]=abs(viz[bk[o]]);
   o++;
   if(viz[bk[o-1]]>0&&mn>c[bk[o]][bk[o-1]]-f[bk[o]][bk[o-1]])
    mn=c[bk[o]][bk[o-1]]-f[bk[o]][bk[o-1]];
   else if(viz[bk[o-1]]<0&&mn>f[bk[o-1]][bk[o]])
    mn=f[bk[o-1]][bk[o]];
   }
  for(i=o;i>1;i--)
   if(viz[bk[i-1]]>0)
    f[bk[i]][bk[i-1]]+=mn;
   else
    f[bk[i]][bk[i-1]]-=mn;
  }
 }
void show()
 {
 long flux=0;
 for(int i=0;i<l[1].size();i++)
  flux+=f[1][l[1][i]];
 FILE *g=fopen("maxflow.out","w");
 fprintf(g,"%ld",flux);
 fclose(g);
 }
int main()
 {
 read();
 solve();
 show();
 return 0;
 }