#include <fstream>
#include <deque>
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
ifstream fi("maxflow.in");
ofstream fo("maxflow.out");

int n,m,i,j,c[1001][1001],viz[1001],t[1001],f[1001][1001],rs=0;
deque< int > q;

int BFS(){
	
	for (i=1; i<=n; i++) viz[i]=0;
	q.push_back(1);
	while (!q.empty())
	{
		int nod=q.front(); q.pop_front();
		for (i=1; i<=n; i++)
		{
			if (c[nod][i]>f[nod][i] && !viz[i])
			{
				viz[i]=1;
				q.push_back(i);
				t[i]=nod;
			}
		}
	}
	
	return viz[n];
}


int main(){
	
	fi >> n >> m;
	for (i=1; i<=m; i++)
	{
		int x,y,z;
		fi >> x >> y >> z;
		c[x][y]=z;
	}
	
	while (BFS())
	{
		for (i=1; i<=n; i++)
		{
			if (c[i][n]>f[i][n])
			{
				int fmin=c[i][n]-f[i][n];
				for (j=i; j!=1; j=t[j])
					fmin=min(fmin,(c[t[j]][j]-f[t[j]][j]));
				for (j=i; j!=1; j=t[j])
				{
					f[t[j]][j]+=fmin;
					f[j][t[j]]-=fmin;
				}
				f[i][n]+=fmin;
				f[n][i]-=fmin;
				rs+=fmin;
			}
		}
	}
	
	fo << rs;
	
	return 0;
}