#include <cstdio>
#include <cstring>

#define file_in "maxflow.in"
#define file_out "maxflow.out"

#define nmax 1111

int n,m;
int c[nmax][nmax];
int f[nmax][nmax];
int viz[nmax];

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

int bfs(){
	
	int p,u,i,nod;
	
	memset(viz,0,sizeof(viz));
	
	int q[nmax];
	p=u=1;
	
	q[p]=1;
    viz[1]=-1;

	while(p<=u){
		
		nod=q[p++];
		for (i=1;i<=n;++i)
			 if (viz[i]==0 && c[nod][i]>f[nod][i]){
				 viz[i]=nod;
				 q[++u]=i;
				 if (i==n)
					 return 1;
			 }
	}
	
	return 0;
}

	
int main(){
	
	int i,j,x,y,z,v,ans=0;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	for (i=1;i<=m;++i){
		
		scanf("%d %d %d", &x, &y, &z);
		
		c[x][y]=z;
	}
	v=0;
	for (;bfs();){
		for (i=1;i<=n;++i){
			if (c[i][n]<=f[i][n] || viz[i]<=0) continue;
			v=c[i][n]-f[i][n];
		for (j=i;j!=1;j=viz[j])
            v=min(v,c[viz[j]][j]-f[viz[j]][j]);
		if (v==0) continue;
		f[i][n]+=v;
		f[n][i]-=v;
		for (j=i;j!=1;j=viz[j])
             f[viz[j]][j]+=v,
             f[j][viz[j]]-=v;
		ans+=v;
		}
	}

printf("%d\n", ans);


	return 0;
	
	
}