#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;
		g->adjList[source].push_back(new edge{ source, sink, capacity });
	}
}

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

int nr0 = 0;
void processPath(graph* g, list<edge*>& path) {

	//processes a dfs path
	int minimum = INT_MAX;
	

	for (auto edg : path) {

		//cout << edg->source << " ";
		minimum = edg->flow < minimum ? edg->flow : minimum;
	}
	if (minimum == 0)
		return;

	for (auto edg : path) {

		edg->flow -= minimum;
		if (edg->flow == 0)
			nr0++;
		edg->reversed->flow += minimum;
	}
	//cout << path.back()->sink << " \n";
}


void edmondsKarp(graph* g, int source, int dest, list<edge*>& path) {

	//runs the algorithm on the graph g, where g must be the rezidual graph of the initial graph
	//returns the maximum flow in the graph from source to dest vertices

	g->visited[source] = true;

	if (source == dest) {
		//process path
		processPath(g, path);
	}

	else {

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

			if (!g->visited[edg->sink])
			{
				if (edg->flow != 0 && nr0 == 0) {
					path.push_back(edg);
					edmondsKarp(g, edg->sink, dest, path);
				}
			}
		}
	}

	if (!path.empty())
	{
		if (path.back()->flow == 0)
			nr0--;
		path.pop_back();
	}
	g->visited[source] = false;
}


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 << "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("graph.in");
	readGraph(g, in);
	in.close();
	int dest = g->vertexCount;
	graph* rezG = getRezidual(g);

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

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

	return 0;
}