#include <stdio.h>
#include <string.h>

#define inf 0x3f3f

int n,m,S,D,c[1010][1010],F[1010][1010],t[1010],flux;

int Q[1010];

FILE *f,*g;


void cit(){
	int i,j,x;
	
	f=fopen("maxflow.in","r");
	
	fscanf(f,"%d %d",&n,&m);
	
	for (; m; --m)
	{
		fscanf(f,"%d %d %d",&i,&j,&x);
		c[i][j]=x;
	}
	
	S=1; D=n;
	
	fclose(f);
}

int BF(int S,int D){
	int p,u,nod,i;
	
	memset(t,0,sizeof(t));
	
	p=u=0;
	
	Q[p]=S;
	t[S]=-1;
	
	for (; p<=u; p++)
	{
		nod=Q[p];
		for (i=1;i<=n;i++)
			if (!t[i] && c[nod][i]>F[nod][i])
			{
				Q[++u]=i; t[i]=nod; 
				if (i==D) return 1;
			}
	}
	return 0;
}

inline int min(int a,int b){
	if (a<b) return a;
	return b;
}


void flux_maxim(){
	int i,j,r;
	for (flux=0; BF(S,D); )
		for (i=1;i<=n;i++)
		{
			if (t[i]==-1 || c[i][D]<=F[i][D]) continue;
			
			r=c[i][D]-F[i][D];
			
			for (j=i; j!=S && j; j=t[j])
				r=min(r,c[t[j]][j]-F[t[j]][j]);
			
			if (!r) continue;
			
			F[i][D]+=r;
			
			F[D][i]-=r;
			
			for (j=i; j!=S; j=t[j])
			{
				F[t[j]][j]+=r;
				F[j][t[j]]-=r;
			}
		flux+=r;
		}
}


void afis(){
	g=fopen("maxflow.out","w");
	fprintf(g,"%d\n",flux);
	fclose(g);
}


int main(){
	cit();
	flux_maxim();
	afis();
	return 0;
}