#include <cstdio>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define NMAX 1001
int F[NMAX][NMAX],C[NMAX][NMAX],viz[NMAX],L[NMAX];
int n,m,s,d;

void citire()
{
 int i;
 FILE *fin=fopen("maxflow.in","r");
 fscanf(fin,"%d %d",&n,&m);
 memset(C,0,sizeof(C)); memset(F,0,sizeof(F));
 for (i=1;i<=m;i++)
  { int x,y,c;
   fscanf(fin,"%d %d %d",&x,&y,&c);
   if (!C[x][y]) {C[x][y]=c; gi[y]++; go[x]++;}
      else C[x][y]+=c;
  }
 s=1; d=n;
 fclose(fin);
}

int bfs()
{ int Q[NMAX],p,u,x,i;
 Q[0]=s; p=u=0;viz[s]=1;
 while (p<=u)
  {
   x=Q[p++];
   for (i=1;i<=n;i++)
    if (!viz[i])
     if (C[x][i]>F[x][i]) {viz[i]=x; Q[++u]=i;}
	else
     if (F[i][x]>0) {viz[i]=-x; Q[++u]=i;}
  }
 return (viz[d]);
}

inline int min(int x, int y)
{
 return (x<y?x:y);
}

void ek()
{ int lg,i,v; int a,b;
 do
  {
   memset(viz,0,sizeof(viz));
   if (!bfs()) return;
   L[0]=d; lg=0; a=b=120000;
   while (L[lg]!=s)
    {
     ++lg;
     L[lg]=abs(viz[L[lg-1]]);
     if (viz[L[lg-1]]>0) a=min(a,C[L[lg]][L[lg-1]]-F[L[lg]][L[lg-1]]);
	else
	if (viz[L[lg-1]]<0) b=min(b,F[L[lg-1]][L[lg]]);
    }
   v=min(a,b);
   for (i=lg;i>0;i--)
    if (viz[L[i-1]]>0) F[L[i]][L[i-1]]+=v;
       else F[L[i-1]][L[i]]-=v;
  }
 while (1);
}


void afisare()
{ int i;
 FILE *fout=fopen("maxflow.out","w");
 long max=0;
 for (i=1;i<=n;i++)
  max+=F[i][d];
 fprintf(fout,"%ld\n",max);
 fclose(fout);
}

int main()
{
 citire();
 ek();
 afisare();
 return 0;
}