// infoarena: problema/maxflow //
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1010;
const int MAXM = 5010;

ifstream in("maxflow.in");
ofstream out("maxflow.out");

vector<int> g[MAXN], vn;
deque<int> q;
vector<int>::iterator it;
int n,m,e[MAXM],i,j,c[MAXN][MAXN],f[MAXN][MAXN],t[MAXN],nod,x,y,z,flux,r,k;

int bfs()
{
	int ret = false;
	for(i=1; i<=n; i++)
		t[i] = 0;
	
	q.clear();
	q.push_front(1);
	while(!q.empty())
	{
		nod = q.front();
		q.pop_front();
		
		for(it=g[nod].begin(); it!=g[nod].end(); it++)
			if(f[nod][*it] < c[nod][*it] && !t[*it])
			{
				if(*it == n)
					ret = true;
				t[*it] = nod;
				q.push_back(*it);
			}
	}
	return ret;
}

int main()
{
	in>>n>>m;
	for(i=1; i<=m; i++)
	{
		in>>x>>y>>z;
		g[x].push_back(y);
		g[y].push_back(x);
		if(y == n)
			vn.push_back(x);
		c[x][y] = z;
	}
	
	while(bfs())
	{
		r = 1<<29;
		for(it=vn.begin(); it!=vn.end(); it++)
		{
			if(t[*it] <= 0)
				continue;
			i = *it;
			r = c[i][n] - f[i][n];
			if(r<=0)
				continue;
			while(i!=1)
			{
				r = min(r, c[t[i]][i] - f[t[i]][i]);
				i = t[i];
			}
			
			i = *it;
			f[*it][n] += r;
			f[n][*it] -= r;
			while(i!=1)
			{
				f[t[i]][i] += r;
				f[i][t[i]] -= r;
				k = t[i];
				i = k;
			}
			flux += r;
		}
	}	
	out<<flux;
	
	return 0;
}