#include<iostream>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

fstream f,g;
int n;
int m;

int a[7500][7500];
int b[7500][7500];
int viz[7500];
int coada[7500];
int l[7500];
int L[7500];

void bfs(){
	int s=1,e=1;
	coada[s]=1;
	viz[1]=1;
	while(s<=e){
		int i=coada[s];
		for(int j=1;j<=n;j++){
			if(viz[j]==0&&a[i][j]!=0){
				if(b[i][j]<a[i][j]){
					e++;
					viz[j]=i;
					coada[e]=j;
				}else{
					if(b[j][i]>0){
						e++;
						viz[j]=-i;
						coada[e]=j;
					}
				}

			}
		}
		s++;
	}
}

int minim(int x,int y){
	if(x<y) return x;
	return y;
}

int main(){
	f.open("maxflow.in",ios::in);
	g.open("maxflow.out",ios::out);

	f>>n;
	f>>m;

	for(int i=1;i<=m;i++){
		int x,y,z;
		f>>x;
		f>>y;
		f>>z;
		a[x][y]=z;
	}

	while(1){
		memset(viz,0,(n+1)*sizeof(int));
		memset(coada,0,(n+1)*sizeof(int));

		bfs();
		if(coada[n]==0) break;

		// lantul de ameliorare
		L[1]=n;
		int from=1;
		while(1){
			from++;
			L[from]=abs(viz[L[from-1]]);
			if(L[from]==1) break;
		}

		for(int i=1;i<=n;i++){
			l[i]=L[from+1-i];
		}

		int aa=32000;
		int bb=32000;

		for(int i=1;i<from;i++){
			if(viz[l[i]]>0){
				aa=minim(aa,a[l[i]][l[i+1]]-b[i][i+1]);
			}else{
				bb=minim(bb,b[i+1][i]);
			}
		}
		int v=min(aa,bb);
		for(int i=1;i<from;i++){
			if(viz[l[i]]>0){
				b[l[i]][l[i+1]]+=v;
			}else{
				b[l[i+1]][l[i]]-=v;
			}
		}
		memset(l,0,(from+1)*sizeof(int));
	}

	int flux=0;
	for(int i=1;i<=n;i++) flux +=b[i][n];
	g<<flux;
	return 0;
}