#include <stdio.h>
#include <vector>
using namespace std;
#define nmax 1001
vector<int> l[nmax];
long c[nmax][nmax],f[nmax][nmax];
int n,C[nmax],k;
int viz[nmax];
void read();
void solve();
void show();
void afis();
int bfs();
int main()
 {
 read();
 solve();
 afis();
 return 0;
 }
void read()
 {
 int x,y,cs,m;
 FILE *f=fopen("maxflow.in","r");
 fscanf(f,"%d %d",&n,&m);
 for(int i=0;i<m;i++)
  {
  fscanf(f,"%d %d %d",&x,&y,&cs);
  c[x][y]=cs;
  l[x].push_back(y);
  }
 }
void solve()
 {
 int lg[nmax],cd=0,x,mn;
 while(bfs())
  {
  cd=0;
  mn=-1;
  k=n;
  lg[++cd]=n;
  do
   {
   if((mn==-1)||(k!=viz[k]&&mn>c[viz[k]][k]-f[viz[k]][k]))
    mn=c[viz[k]][k]-f[viz[k]][k];
   k=viz[k];
   lg[++cd]=k;
   }while(k>1);
  for(int i=1;i<cd;i++)
   f[lg[i+1]][lg[i]]+=mn;
  }
 }
int bfs()
 {
 int i,j,x;
 k=0;
 for(i=1;i<=n;i++) viz[i]=0;
 C[++k]=1;
 viz[1]=1;
 for(i=1;i<=k&&C[k]!=n;i++)
  {
  x=C[i];
  for(j=0;j<l[x].size()&&C[k]!=n;j++)
   {
   if(!viz[l[x][j]])
    if(c[x][l[x][j]]>f[x][l[x][j]])
     {
     C[++k]=l[x][j];
     viz[l[x][j]]=x;
     }
   }
  }
 return viz[n];
 }
void afis()
 {
 long v=0;
 for(int i=0;i<l[1].size();i++)
  v+=f[1][l[1][i]];
 FILE *g=fopen("maxflow.out","w");
 fprintf(g,"%ld",v);
 }