#include <vector>
#include <stdio.h>
using namespace std;
#define abs(x) ((x>0)?(x):(-(x)))
#define min(x,y) ((x<y)?(x):(y))
#define nmax 1001
int n,Cd[nmax],pre[nmax];
long C[nmax][nmax],F[nmax][nmax];
bool viz[nmax];
vector<int> l[nmax];
void read()
 {
 FILE *f=fopen("maxflow.in","r");
 int m,x,y;
 long c;
 fscanf(f,"%d %d",&n,&m);
 for(int i=1;i<=m;i++)
  {
  fscanf(f,"%d %d %ld",&x,&y,&c);
  C[x][y]+=c;
  l[x].push_back(y);
  l[y].push_back(x);
  }
 }
bool bfs()
 {
 int j,i,nr=0,y,x;
 for(i=1;i<=n;i++) viz[i]=false,pre[i]=0;
 Cd[++nr]=1;
 viz[1]=true;
 for(i=1;i<=nr;i++)
  {
  x=Cd[i];
  if(x==n)
   continue;
  for(j=0;j<l[x].size();j++)
   {
   y=l[x][j];
   if(F[x][y]<C[x][y]&&!viz[y])
    {
    pre[y]=x;
    Cd[++nr]=y;
    viz[y]=1;
    }
   }
  }
 return viz[n];
 }
void solve()
 {
 int i,j,d[nmax],m,x;
 long f;
 while(bfs())
  {
  for(i=0;i<l[n].size();i++)
   {
   x=l[n][i];
   if(!viz[x]||C[x][n]==F[x][n])
    continue;
   m=0;
   f=110999;
   pre[n]=x;
   for(j=n;j>0;j=pre[j])
    {
    d[++m]=j;
    }
   for(j=1;j<m;j++)
    {
    f=min(f,abs(C[d[j+1]][d[j]]-F[d[j+1]][d[j]]));
    }
   if(f==0)
    continue;
   for(j=1;j<m;j++)
    F[d[j+1]][d[j]]+=f,F[d[j]][d[j+1]]-=f;
   }
  }
 }
void show()
 {
 long f=0;
 int i;
 FILE *g=fopen("maxflow.out","w");
 for(i=0;i<l[1].size();i++)
  f+=C[1][l[1][i]];
 fprintf(g,"%ld",f);
 
 }
int main()
 {
 read();
 solve();
 show();
 return 0;
 }