#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;
};

graph* rG = new graph;
void readGraph(graph* g, ifstream& in) {

	//reads the graph data
	in >> g->vertexCount >> g->edgeCount;
	rG->vertexCount = g->vertexCount;
	rG->edgeCount = 2 * g->edgeCount;
	
	rG->adjList = new list<edge*>[rG->vertexCount + 1];
	rG->visited = new bool[rG->vertexCount + 1];
	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, rG->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);


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

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



		rG->adjList[e->source].push_back(e);
		rG->adjList[revEdge->source].push_back(revEdge);
	}
}


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();

		if (crt == dest) {
			continue;
		}

		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 fordFulkerson(graph* g, int source, int dest) {


	vector<edge*> parent(g->vertexCount + 1);

	int flow = 0;
	while (getPath(g, source, dest, parent)) {
		edge* k;
		for(auto elem:g->adjList[dest]){
			if (!g->visited[elem->sink] || elem->flow == elem->capacity)
				continue;
			k = elem;

		parent[dest] = k->reversed;

	
		list<edge*> path;
		int crt = dest;
		int mini = parent[crt]->flow;
		while (crt != source) {
			path.push_back(parent[crt]);
			
			edge* edg = parent[crt];
			crt = parent[crt]->source;
			mini = mini < edg->flow ? mini : edg->flow;
		}
		flow += mini;

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

	ofstream out("maxflow.out");
	out << flow;
	out.close();

}

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;
}





int main() {


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


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

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

	

	return 0;
}