#include <iostream>
#include <fstream>
#include <stack>
#include <queue>
#include <list>

using namespace std;




struct edge {

	int source;		//
	int sink;		//the two vertices
	int capacity;
	int flow = 0;
	edge* reversed = NULL;
	bool isReverted = false;
};

struct graph {

	int vertexCount, edgeCount;			//graph dimension
	list<edge*>* adjList;				//adjList[i] contains all the edges leaving from i
	bool* visited;
};

void readGraph(graph* g, ifstream& in) {

	//reads the graph data
	in >> g->vertexCount >> g->edgeCount;

	g->adjList = new list<edge*>[g->vertexCount + 1];
	g->visited = new bool[g->vertexCount + 1];
	for (int i = 1; i <= g->vertexCount; i++)
		g->visited[i] = false;

	for (int i = 1; i <= g->edgeCount; i++) {

		int source, sink, capacity;
		in >> source >> sink >> capacity;
		edge* e = new edge;
		e->source = source;
		e->sink = sink;
		e->capacity = capacity;
		g->adjList[source].push_back(e);
	}
}

graph* getRezidual(graph* g) {

	//returns a newly built rezidual graph for the parameter graph
	graph* rezGraph = new graph;

	rezGraph->vertexCount = g->vertexCount;
	rezGraph->edgeCount = 2 * g->edgeCount;

	rezGraph->adjList = new list<edge*>[rezGraph->vertexCount + 1];
	rezGraph->visited = new bool[rezGraph->vertexCount + 1];
	for (int i = 1; i <= rezGraph->vertexCount; i++)
		rezGraph->visited[i] = false;

	for (int i = 1; i <= g->vertexCount; i++) {
		for (auto edg : g->adjList[i]) {			//for each edge in the normal graph

			edg->flow = edg->capacity;				//not yet consumed
			edge* revEdge = new edge;				//create the reversed edge
			revEdge->flow = 0;						//not yet consumed
			revEdge->source = edg->sink;
			revEdge->sink = edg->source;
			revEdge->capacity = edg->capacity;
			edg->isReverted = false;
			revEdge->isReverted = true;

			revEdge->reversed = edg;		//set reversed
			edg->reversed = revEdge;		//



			rezGraph->adjList[edg->source].push_back(edg);
			rezGraph->adjList[revEdge->source].push_back(revEdge);
		}
	}

	return rezGraph;
}

bool getPath(graph* g, int source, int dest, vector<edge*>& parent) {

	for (int i = 1; i <= g->vertexCount; i++)
		g->visited[i] = false;

	list<int> queue;
	queue.push_back(source);
	g->visited[source] = true;

	while (!queue.empty()) {
		int crt = queue.front();
		queue.pop_front();

		for (auto edg : g->adjList[crt]) {

			if (edg->flow > 0 && !g->visited[edg->sink]) {
				g->visited[edg->sink] = true;
				parent[edg->sink] = edg;
				queue.push_back(edg->sink);
			}
		}
	}
	return  g->visited[dest];
}


void processPath(graph* g, list<edge*> path) {

	if (path.empty())
		return;

	int mini = path.front()->flow;

	for (auto edg : path) {
		mini = mini < edg->flow ? mini : edg->flow;
	}

	for (auto edg : path) {
		edg->flow -= mini;
		edg->reversed->flow += mini;
	}
}


void fordFulkerson(graph* g, int source, int dest) {


	vector<edge*> parent(g->vertexCount + 1);
	while (getPath(g, source, dest, parent)) {

		list<edge*> path;
		int crt = dest;
		while (crt != source) {
			path.push_back(parent[crt]);
			crt = parent[crt]->source;
		}
		processPath(g, path);
	}
}

void printFlow(graph* g, int source, int dest, ofstream& out) {

	int totalFlow = 0;

	for (auto edg : g->adjList[source]) {
		if (!edg->isReverted)
			totalFlow += edg->reversed->flow;
	}
	out << totalFlow;
	
	//out << "Total flow: " << totalFlow << "\n";

	/*for (int i = 1; i <= g->vertexCount; i++) {
		for (auto edg : g->adjList[i]) {

			if (!edg->isReverted) {
				out << edg->source << " -> " << edg->sink << ": " << edg->reversed->flow << " units.\n";
			}
		}
	}	*/
}





int main() {


	graph* g = new graph;
	int source = 1;


	ifstream in("maxflow.in");
	readGraph(g, in);
	in.close();
	int dest = g->vertexCount;
	graph* rezG = getRezidual(g);

	list<edge*> lst;
	fordFulkerson(rezG, source, dest);

	ofstream out("maxflow.out");
	printFlow(rezG, source, dest, out);
	out.close();

	return 0;
}