#pragma once

#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<map>


using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

class Node {
public:
	int id;

	unordered_map<int, pair<int, int>> adj; // key - adj node id, value - flow/capacity pair, using a map to easily update flows from a path i found
	void add(int id, int f, int cap) {
		adj[id] = make_pair(f, cap);
	}
};


vector<Node> nodes;
int V, E, _inf = 1<<21;

int updatePath(vector<int> &parents) {
	int c = nodes.back().id, start, end, minim = _inf;
	pair<int,int> fc, fc2;
	while (parents[c] != 0) { // while we have a parent  
		// we need to first determine bottleneck value
		// we need to take the capacity - flow for each edge
		// the edge in the found path is parents[c] -> c
		start = parents[c];
		end = c;
		fc = nodes[start].adj[end];
		if (fc.second - fc.first < minim)
			minim = fc.second - fc.first;
		c = start;
	}
	// update values with found bottleneck
	c = nodes.back().id;
	while (parents[c] != 0) {
		// we need to find both initial edges and residual ones, to check which one is which we look at the capacity
		start = parents[c];
		end = c;
		fc = nodes[start].adj[end];
		fc2 = nodes[end].adj[start];

		if (fc.second > 0) { // => start - end is a real edge => end - start is a residual edge
			nodes[start].adj[end] = make_pair(fc.first + minim, fc.second); // same capacity, added minim to the flow
			nodes[end].adj[start] = make_pair(fc2.first - minim, 0); // add the negative, this means this edge can reverse flow
		}
		else {
			nodes[start].adj[end] = make_pair(fc.first + minim, 0); 
			nodes[end].adj[start] = make_pair(fc2.first - minim, fc2.second); 
		}
		c = start;
	}

	return minim;

}

int augmentPath() {
	int source = 1, sink = nodes.back().id, adjID, found = 0;
	pair<int, int> fc;
	queue<int> bfsQ;
	vector<int> parents(V+1,0), seen(V+1,0);
	bfsQ.push(source);


	while (!bfsQ.empty()) {
		int c = bfsQ.front();
		bfsQ.pop();

		seen[c] = 1;

		if (c == sink) {
			found = 1;
			break; // found a path
		}

		for (auto x : nodes[c].adj) {
			adjID = x.first;
			fc = x.second;

			if (fc.first < fc.second && seen[adjID] == 0) { // flow less than capacity and adj node was not already seen => good edge

				bfsQ.push(adjID); // push the adjacent node
				parents[adjID] = c;

			}

		}
	}
	if (found) 
		return updatePath(parents);
		
	return 0;

}

int maxFlow() {
	int flow = 0, f;
	while ((f = augmentPath()) != 0) {
		flow += f;
	}
	return flow;
}

int main() {
	int x, y, cap;
	fin >> V >> E;
	nodes.resize(V+1);
	for (int i = 0; i <= V; i++)
		nodes[i].id = i;
	for (int i = 0; i < E; i++) {
		fin >> x >> y >> cap;
		nodes[x].add(y, 0, cap);
		nodes[y].add(x, 0, 0); // initially no flow, so there can be no flow back

		// NOTE: residual graph edges will have 0 capacity and negative flow indicatind that these edges are for turning back flow
	}
	fout << maxFlow();

	return 0;
}