//#include <iostream>
//#include <fstream>
//#include <string>
//#include <vector>
//#include <queue>
//#include <math.h>

#include <bits/stdc++.h>

int Bfs(int Sursa, int Dest, std::vector< int >& Parent, std::vector < std::vector < int > > Graf);
int EdmondsKarp(std::vector < std::vector < std::pair < int, int > > > Graf, int Sursa, int Dest);

void Problema1(std::string InFile, std::string OutFile)
{
	int nrNoduri, nrMuchii, sursa, dest, cost;
	std::vector < std::vector < std::pair < int, int > > > graf;

	std::ifstream in(InFile);

	in >> nrNoduri >> nrMuchii;

	graf = std::vector < std::vector < std::pair < int, int > > >(nrNoduri);

	for (int muchie = 0; muchie < nrMuchii; muchie = muchie + 1)
	{
		in >> sursa >> dest >> cost;
		graf[sursa].push_back({ dest, cost });
	}

	in.close();

	std::ofstream out(OutFile);

	out << EdmondsKarp(graf, 0, nrNoduri - 1);

	out.close();
}


int main()
{
	Problema1("maxflow.in", "maxflow.out");
	return 0;
}

int Bfs(int Sursa, int Dest, std::vector< int >& Parent, std::vector < std::vector < int > > Graf)
{
	int current, flow, newFlow;
	std::queue < std::pair < int, int > > bfsQueue;

	std::fill(Parent.begin(), Parent.end(), -1);
	Parent[Sursa] = -2;

	bfsQueue.push({ Sursa, INT_MAX });

	while (false == bfsQueue.empty())
	{
		current = bfsQueue.front().first;
		flow = bfsQueue.front().second;
		bfsQueue.pop();

		for (int vecin = 0; vecin < (int)Graf.size(); vecin = vecin + 1)
		{
			if (-1 == Parent[vecin] && Graf[current][vecin])
			{
				Parent[vecin] = current;
				newFlow = (flow < Graf[current][vecin]) ? flow : Graf[current][vecin];
				if (Dest == vecin)
					return newFlow;
				bfsQueue.push({ vecin, newFlow });
			}
		}
	}
	return 0;
}

int EdmondsKarp(std::vector < std::vector < std::pair < int, int > > > Graf, int Sursa, int Dest)
{
	int flow = 0, newFlow, nrNoduri = (int)Graf.size(), current, prev;
	std::vector < std::vector < int > > rGraf(nrNoduri, std::vector < int >(nrNoduri, 0));
	std::vector < int > parent(nrNoduri);

	for (int nod = 0; nod < nrNoduri; nod = nod + 1)
	{
		for (auto vecin : Graf[nod])
		{
			rGraf[nod][vecin.first] = vecin.second;
		}
	}

	while (newFlow = Bfs(Sursa, Dest, parent, rGraf))
	{
		flow = flow + newFlow;
		current = Dest;
		while (Sursa != current)
		{
			prev = parent[current];
			rGraf[prev][current] = rGraf[prev][current] - newFlow;
			rGraf[current][prev] = rGraf[current][prev] + newFlow;
			current = prev;
		}
	}

	return flow;
}