#include<stdio.h>
#define maxv 5000
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?x:-x)

int n,m,s,d,viz[maxv],q[maxv],C[maxv][maxv],F[maxv][maxv];

FILE *f=fopen("maxflow.in","r"), *g=fopen("maxflow.out","w");

void citire(void);
void afisare(void);
void ek(void);
int bfs(void);

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

void citire()
{
int i,x,y,c;

fscanf(f,"%d%d",&n,&m); s=1; d=n;
 for(i=0;i<m;i++)
  {fscanf(f,"%d%d%d",&x,&y,&c); C[x][y]=c;}
  
}

void afisare()
{int i,j,vf=0;

/*for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
	if(F[i][j])
	fprintf(g,"Fluxul arcului %d %d=%d\n",i,j,F[i][j]);*/
	
for(i=1;i<=n;i++) vf+=F[i][d];
fprintf(g,"%d\n",vf);
}

void ek()
{int i,a,b,lg,v;
int L[maxv];

do
{
 for(i=1;i<=n;i++) viz[i]=0;
 if(bfs()) return;
 L[0]=d; lg=0;
 a=b=10000;
 
 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);
}

int bfs()
{int p,u,i,x;
q[0]=s; p=u=0; viz[s]=1;

 while(p<=u && !viz[d])
 {x=q[p++];
  for(i=1;i<=n;i++)
	if(!viz[i]) 
		if(F[x][i]<C[x][i])
		{viz[i]=x; q[++u]=i;}
	else if(F[i][x]>0) {viz[i]=-x; q[++u]=i;}
 }
 return !viz[d];
}