#include<stdio.h>
using namespace std;
#define dim 1005
#define dim2 5005
#include<math.h>
#define abs(x) ((x)>0?x:-x)
int A[dim][dim][2], n,st,fin,gasit,coada[dim2],s[dim],ic,sfc,i,j,min,S;

void citire()
{	int i,m,x,y,c;
	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);
	
	A[x][y][0]=c;	
	}
}

void refac (int Nod)
{
	if(Nod!=st)
		if(s[Nod]>0)
		{
			if(min>A[ s[Nod] ][Nod][0]-A[s[Nod]][Nod][1])
				min=A[s[Nod]  ][Nod][0]-A[s[Nod]][Nod][1];
			
			refac(s[Nod]);
			A[s[Nod]][Nod][1]+=min;
		
		}
		
	else {
		if( min > A[Nod][ s[ abs(Nod) ]][1] )
			min= A[Nod][ abs(s[Nod]) ][1] ;
		refac(abs(s[Nod]));
		 A[Nod][abs(s[Nod])][1]-=min;
	}
	

}


void drum_in_crestere()
{

	gasit=0;
	ic=sfc=1;
	coada[ic]=st;
	while( (ic<=sfc) && coada[sfc]!=fin )
	{
		i=1;
		while(i<=n&&!gasit)
		{
		if( (A[coada[ic]][i][0]-A[coada[ic]][i][1]>0 ) &&s[i]==0 )
		{
			s[i]=coada[ic];
			coada[++sfc]=i;
		
		}
		else if(( A[i][coada[ic]][1]>0 ) && (s[i]==0)&&i!=st)
		{
		s[i]=-coada[ic];
		coada[++sfc]=i;
		}
		i++;
		}
	ic++;
	
	}
	if(coada[sfc]==fin)
		gasit=1;

}

void caut()
{

	do
	{
		for(i=1;i<=n;i++)
			s[i]=0;
		drum_in_crestere();
		if(s[fin])
		{
			min=32000;
			refac(fin);
		}
			
	}while(gasit);
	
}


int main()
{
	FILE *g=fopen("maxflow.out","w");
	
	citire();
	st=1; fin=n;
	caut();
	
	for(i=1;i<=n;i++)
	{
		S+=A[1][i][1];
	}
	
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			fprintf(g,"%d ",A[i][j][1]);
		fprintf(g,"\n");
	}*/

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

return 0;
}