#include <stdio.h>
#include <vector>
using namespace std;
#define nmax 1001
vector<int> l[nmax];
int c[nmax][nmax],f[nmax][nmax];
int n,C[nmax],k;
bool 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;
  x=k-1;
  lg[++cd]=n;
  while(x>0)
   {
   if(viz[C[x]]&&c[C[x]][C[k]]&&f[C[x]][C[k]]<c[C[x]][C[k]])
    {
    lg[++cd]=C[x];
    if(mn==-1||mn>c[C[x]][C[k]]-f[C[x]][C[k]])
     {
     mn=c[C[x]][C[k]]-f[C[x]][C[k]];
     }
    k=x;
    }
   x--;
   }
  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();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]]=1;
     }
   }
  }
 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);
 }