#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 1002
#define MMAX 5002
int F[NMAX][NMAX],C[NMAX][NMAX],viz[NMAX],L[NMAX],grad[NMAX];
struct muchie {int x, y;} M[MMAX];
int n,s,d,nm,*vec[NMAX];

void citire()
{
 int i,m;
 FILE *fin=fopen("maxflow.in","r");
 fscanf(fin,"%d %d",&n,&m);
 memset(C,0,sizeof(C)); memset(F,0,sizeof(F)); memset(grad,0,sizeof(grad));
 nm=0;
 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; M[++nm].x=x; M[nm].y=y; grad[x]++; grad[y]++;}
      else C[x][y]+=c;
  }
 for (i=1;i<=n;++i) { vec[i]=(int*)realloc(vec[i],sizeof(int)*(grad[i]+1));vec[i][0]=0;}
 for (i=1;i<=nm;++i)
  { int x=M[i].x,y=M[i].y;
   vec[x][++vec[x][0]]=y;
   vec[y][++vec[y][0]]=x;
  }
 s=1; d=n;
 fclose(fin);
}

int bfs()
{ int Q[NMAX],p,u,x,i,h;
 Q[0]=s; p=u=0;viz[s]=1;
 while (p<=u)
  {
   x=Q[p++];
   if (x==d) continue;
   for (h=1;h<=grad[x];++h)
    { i=vec[x][h];
    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,ok,x,j;
 memset(viz,0,sizeof(viz));
 while (bfs())
  {
   for (j=1;j<=grad[d];++j)
    {
     x=vec[d][j];
     if (F[x][d]<C[x][d]&&viz[x])
     {
      viz[d]=x;
      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;
     }
    }
     memset(viz,0,sizeof(viz));
  }
}


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;
}