#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
typedef struct {
	int v;
	map <int, int> n;
	map <int, int> c;
} node;
vector <int> parent;
vector <node> nodes;
vector <int> ng;

int n, m;
bool bfs ()
{
	int u;
	queue <int> queue;
	parent.assign(n,-1);
	queue.push(1);
	bool ok = false;
	while (!queue.empty())
	{
		u = queue.front();
		queue.pop();
		for (map<int,int>::iterator it = nodes[u].n.begin(); it != nodes[u].n.end(); it++)
		{
			if ((*it).second - nodes[u].c[(*it).first] != 0 && (*it).first != n && parent [(*it).first] == -1)
			{
				parent[(*it).first] = u;
				queue.push((*it).first);
			}
			if ((*it).first == n && (*it).second - nodes[u].c[(*it).first] > 0)
				ok = true;
		}
	}
	return ok;
}
int mini (int x)
{
	int mins = 100000;
	for (int j = x; j != 1; j = parent[j])
	{
		mins = min (mins, nodes[parent[j]].n[j] - nodes[parent[j]].c[j]);
	}
	mins = min(mins, nodes[x].n[n] - nodes[x].c[n]);
	return mins;
}
int maxflow ()
{
	int f, s;
	long int flow = 0;
	while (bfs())
	{
		f = 0;
		for (int i = 0; i < ng.size(); i++)
		{
			if (parent[ng[i]] != -1 && nodes[ng[i]].n[n] - nodes[ng[i]].c[n] > 0)
			{
				//cout << ng[i] << " ";
				f = mini (ng[i]);
				if (f > 0)
				{
					flow += f;
					nodes[ng[i]].c[n] += f;
					if (nodes[n].c.find(ng[i]) != nodes[n].c.end())
						nodes[n].c[ng[i]] -= f;
		
					s = ng[i];
				//	cout << "drum " <<f << endl;
					while (s != 1)
					{
						nodes[parent[s]].c[s] += f;
						if (nodes[s].c.find(parent[s]) != nodes[s].c.end())
							nodes[s].c[parent[s]] -= f;
			
			//			cout << s << " ";
						s = parent[s];

					}
				//	cout << endl;
				}
			}
		}
	}
	return flow;
}

int main ()
{
	ifstream in ("maxflow.in");
	ofstream out ("maxflow.out");
	
	in >> n >> m;
	int x, y, c;
	nodes.resize(n + 1);
	for (int i = 0; i < m ; i++)
	{
		in >> x >> y >> c;
		nodes[x].n.insert (pair <int, int> (y,c));
		nodes[x].c.insert (pair <int, int> (y,0));
		if (y == n)
			ng.push_back(x);
	}
	
	out << maxflow();
	return 0;
}