#include <fstream>
#include <list>
#include <queue>

using namespace std;

struct edge {

	int source, sink, flow;
	edge* reverted;
};

struct graph {

	int vertexCount, edgeCount;
	list<edge*>* adjList;
};

void readGraph(graph& g, ifstream& in) {
	in >> g.vertexCount >> g.edgeCount;
	g.adjList = new list<edge*>[g.vertexCount + 1];

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

		int source, sink, flow;
		in >> source >> sink >> flow;

		edge* normal = new edge{ source,sink, flow };
		edge* reverted = new edge{ sink, source, 0, normal };
		normal->reverted = reverted;

		g.adjList[source].push_back(normal);
		g.adjList[sink].push_back(reverted);
	}
}

bool BFS(graph& g, int source, int sink, edge** parent, bool* visited) {

	for (int i = 1; i <= g.vertexCount; i++) {
		visited[i] = false;
		parent[i] = NULL;
	}

	queue<int> queue;
	queue.push(source);
	visited[source] = true;

	while (!queue.empty()) {

		int crt = queue.front();
		queue.pop();

		if (crt == sink)
			continue;

		for (auto adj : g.adjList[crt]) {

			if (adj->flow > 0 && !visited[adj->sink]) {

				visited[adj->sink] = true;
				parent[adj->sink] = adj;
				queue.push(adj->sink);
			}
		}
	}

	bool viz = visited[sink];
	return viz;
}


int fordFulkerson(graph& g, int source, int sink) {

	int flow = 0;
	edge** parent = (edge**)malloc((g.vertexCount + 1) * sizeof(edge*));
	bool* visited = (bool*)malloc((g.vertexCount + 1) * sizeof(bool));

	while (BFS(g, source, sink, parent, visited)) {

		for (auto edg : g.adjList[sink]) {

			if (edg->reverted->flow > 0 && visited[edg->sink]) {

				parent[sink] = edg->reverted;

				edge* crt = edg->reverted;
				int mini = crt->flow;
		
				while (crt != NULL){
					mini = mini < crt->flow ? mini : crt->flow;
					crt = parent[crt->source];
				}

				crt = edg->reverted;

				while (crt != NULL){
					crt->flow -= mini;
					crt->reverted->flow += mini;
					crt = parent[crt->source];
				}

				flow += mini;
			}
		}
	}

	free(parent);
	free(visited);
	return flow;
}


















int main() {

	graph g;

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

	int flow = fordFulkerson(g, 1, g.vertexCount);

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


	return 0;
}