#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define FI fopen("maxflow.in","r")
#define FO fopen("maxflow.out","w")

long long sol;
long mat[1001][1001];
int n;
vector<int> nod[1001];

void citeste(FILE *f) {
	int i,m,a,b;
	long c;
	fscanf(f,"%i%i",&n,&m);
	for(i=0;i<m;i++) {
		fscanf(f,"%i%i%li",&a,&b,&c);
		if(a==1 && b==n) {
			sol+=c;
			continue;
		}
		mat[a][b]=c;
		nod[a].push_back(b);
		nod[b].push_back(a);
	}
}

int createArbore(int par[],int sf[],int &sfLen) {
	int i,j,k,lim,st[1001];
	char viz[1001];
	for(i=2;i<n;i++)
		viz[i]=0;
	st[0]=1;
	viz[1]=1;
	i=0;
	j=1;
	sfLen=0;
	while(i<j) {
		lim=nod[st[i]].size();
		for(k=0;k<lim;k++)
			if(viz[nod[st[i]][k]]==0 && mat[st[i]][nod[st[i]][k]]) {
				if(nod[st[i]][k]==n) {
					sf[sfLen]=st[i];
					sfLen++;
				}
				else {
					par[nod[st[i]][k]]=st[i];
					viz[nod[st[i]][k]]=1;
					st[j]=nod[st[i]][k];
					j++;
				}
			}
		i++;
	}
	return sfLen;
}

long long min(long long a,long long b) { if(a<b) return a; return b; }
long parcurge(int par[],int nodAct,int nodAnt,long long max) {
	if(nodAct == 1) {
		max=min(max,mat[nodAct][nodAnt]);
		mat[nodAct][nodAnt]-=max;
		mat[nodAnt][nodAct]+=max;
		return max;
	}
	max=parcurge(par,par[nodAct],nodAct,min(mat[nodAct][nodAnt],max));
	mat[nodAct][nodAnt]-=max;
	mat[nodAnt][nodAct]+=max;
	return max;
}

void flux() {
	int i,par[1001],sf[1000],sfLen;
	while(createArbore(par,sf,sfLen))
		for(i=0;i<sfLen;i++)
			sol+=parcurge(par,sf[i],n,0x7fffffffffffffffll);
}

int main() {
	citeste(FI);
	flux();
	fprintf(FO,"%lli",sol);
	return 0;
}