#include <iostream>
#include <fstream>
#define inf 1111111

using namespace std;

int f[1000][1000], viz[1000], c[1000][1000],i,q[1000],x,y,p,u,n,m,a,b,v,l[1000],lg;


bool bfs() {
	p=1;u=1;
	viz[1]=1;
	q[1]=1;
	while (p<=u && viz[n]==0) {
		x=q[p++];
		for (i=1; i<=n; i++) {
			if (viz[i]==0) 
				if (f[x][i]<c[x][i])  {
					viz[i]=x;
					q[++u]=i;
				}
				else {
					if (f[i][x]>0)  {
					viz[i]=-x;
					q[++u]=i;
					}
				}
		}
	}
	return !viz[n];
}

void ek() {
	while(1) {
	for (i=1; i<=n; i++)
		viz[i]=0;
	if (bfs()) return;
	else {
		a=b=inf;
		l[1]=n;
		lg=1;
		while (l[lg]!=1) {
			lg++;
			l[lg]=abs(viz[l[lg-1]]);
			if (viz[l[lg-1]]>0)
				a=min(a,c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]);
			else
			if (viz[l[lg-1]]<0)
				b=min(b, f[l[lg]][l[lg-1]]);
		}
		v=min(a,b);
		for (i=lg; i>1; i--)
			if (viz[l[i-1]]>0)
				f[l[i]][l[i-1]]+=v;
			else
				f[l[i]][l[i-1]]-=v;
	}
	}
}
			
int main() {
	ifstream r("maxflow.in");
	ofstream g("maxflow.out");
	r>>n>>m;
	for (i=1; i<=m; i++)
		r>>x>>y>>c[x][y];
	ek();
	v=0;
	for (i=1; i<=n; i++)
		if (f[i][n]!=0)
			v+=f[i][n];
	g<<v;
	g.close();
	return 0;
}