#include <fstream>
#include <iostream>
#include <list>

using namespace std;

struct edge {

	int source;
	int sink;
	int flow;
	bool isReversed;
	bool visited;
	edge* reversed;
};


struct graph {

	int vertexCount;
	int edgeCount;
	bool* visited;
	list<edge*>* adjList;
};


///////////////////////////////////////// Read & constructors

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

	in >> g.vertexCount >> g.edgeCount;
	g.adjList = new list<edge*>[g.vertexCount + 1];
	g.visited = (bool*)calloc(g.vertexCount + 1, sizeof(bool));

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

		int source, sink, flow;
		in >> source >> sink >> flow;
		
		edge* edg = new edge{ source, sink, flow , false , false ,NULL};

		g.adjList[source].push_back(edg);
	}
}

graph* getReversed(graph& g) {
	
	graph* rev = new graph{ g.vertexCount, g.edgeCount };
	rev->adjList = new list<edge*>[g.vertexCount + 1];
	rev->visited = (bool*)calloc(g.vertexCount + 1, sizeof(bool));

	for (int i = 1; i <= g.vertexCount; i++) {
		for (auto edg : g.adjList[i]) {
			if (!edg->isReversed) {
		
				edge* revEdg = new edge{ edg->sink, edg->source, 0, true, false,NULL };
				edge* normEdg = new edge{ edg->source, edg->sink, edg->flow, false, false, revEdg };
				revEdg->reversed = normEdg;
				rev->adjList[edg->source].push_back(normEdg);
				rev->adjList[edg->sink].push_back(revEdg);
			}
		}
	}
	return rev;
}








//////////////////////////////// Algorithm
int flow = 0;

int getFlow(graph* g, int dest) {

	int flow = 0;
	for (auto edg : g->adjList[dest]) {
		if (edg->isReversed)
			flow += edg->flow;
	}
	return flow;
}
int nr0 = 0;
void processPath(list<edge*> path) {

	if (path.empty())
		return;

	int minimFlow = (*path.begin())->flow;

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

	if (minimFlow == 0)
		return;

	for (auto edg : path) {
		edg->flow -= minimFlow;
		
		edg->reversed->flow += minimFlow;
		if (edg->flow == 0)
			nr0++;
	}
	flow += minimFlow;
}

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

	if (source == dest) {
		processPath(path);
	}

	else {
		for (auto edg : g->adjList[source]) {
			if (!g->visited[edg->sink] && edg->flow > 0 && nr0==0) {
				path.push_back(edg);
				g->visited[edg->sink] = true;
				DFS(g, edg->sink, dest, path);
			}
		}
	}

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

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

	g->visited[source] = true;
	list<edge*> path;
	DFS(g,source, dest, path);
}





int main() {

	graph g;
	

	ifstream in("maxflow.in");
	readGraph(g, in);
	in.close();

	int source = 1;
	int sink = g.vertexCount;

	graph* revGraph = getReversed(g);


	getPaths(revGraph, source, sink);

	ofstream out("maxflow.out");
	out << flow;// getFlow(revGraph, sink);
	out.close();

	return 0;
}