#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define dim 1005 
using namespace std;

int A[dim][dim],F[dim][dim],n,m,i,x,y,c,coada[dim],viz[dim],min,u[dim],s,d,j,ok,in,sf,flux;


void citire()
{
	FILE *f=fopen("maxflow.in","r");
	
fscanf(f,"%d %d",&n,&m);

for(i=1;i<=m;i++)
{
	fscanf(f,"%d %d %d",&x,&y,&c);
	
	//coada[y]=1;	
	//viz[x]=1; 
	
	A[x][y]=c;
	A[y][x]=-c;
}


fclose(f);
}

void bfs(int x)
{
	
	
	viz[x]=1;
	coada[1]=x; in=sf=1; u[1]=0;
	
	while(in<=sf)
	{
	x=coada[in++];
	for(i=1;i<=n;i++)
		if(A[x][i]!=0 && ! viz[ i ] &&A[x][i]!=F[x][i] )
			{
			if( A[x][i]>0 || (A[x][i]<0 && F[i][x]!=0) )
			{
				if(i==d)
					{coada[++sf]=d; ok=1; u[sf]=in-1; return;}
			
				viz[i]=1;
				coada[++sf]=i;
				u[sf]=in-1;		
			}
				
			}
	}
	ok=0;
	return;


}


int main()
{
	FILE *g=fopen("maxflow.out","w");
	citire();
/*
for(i=1;i<=n;i++)	
	if(coada[i]==0)
		{s=i;break;}
		
for(i=1;i<=n;i++)	
	if(viz[i]==0)
		{d=i;break;}
	
memset(coada,0,sizeof(coada));	
memset(viz,0,sizeof(viz));	
	*/
	s=1; d=n;

	ok=1;
	while(ok)
	{
		
		bfs(s);
		min=110000;
		if(ok)
		{
		for(j=sf;j>1;j)
		{
			x=coada[u[j]];
			y=coada[j];
			
			if(A[x][y]<0)
				{if(F[y][x]<min)
				min=F[y][x];}
			else		
			if(A[x][y]-F[x][y]<min)
				min=A[x][y]-F[x][y];
			
		j=u[j];
		}
		
		for(j=sf;j>1;j)
		{
			x=coada[u[j]];
			y=coada[j];
			
			if(A[x][y]>0)
				F[x][y]+=min;
			else F[y][x]-=min;
			
		j=u[j];
		}
			
		memset(coada,0,sizeof(coada));	
		memset(viz,0,sizeof(viz));	
		}
		
		
	}
	
for(i=1;i<=n;i++)
	flux+=F[s][i];

fprintf(g,"%d\n",flux);

return 0;
}