#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <utility>
#include <cstdlib>
#include <algorithm>

typedef std::vector<std::pair<int, int> > graph_node;
typedef std::vector<graph_node > graph;
typedef std::map < int, std::pair<int, int> > flow_node;
typedef std::vector < flow_node > flow_graph;

graph g;

#define Inf 99999999


class MaxFlow {
#define preflow second.second
#define capacity second.first
#define pair_preflow second
#define pair_capacity first
#define to first
	flow_graph r;
	std::vector<int> x;
	std::vector<int> l;
	std::vector<int> count;
	std::vector<bool> active;
	std::vector<std::vector<int> > B;
	int b = 0, n;

	void relabel(int nod) {
		count[l[nod]]--;
		l[nod] = n;
		for (auto it : r[nod]) {
			if (it.capacity > it.preflow)
				l[nod] = std::min(l[nod], l[it.to] + 1);
		}
		count[l[nod]]++;
		enqueue(nod);
	}

	void push(int nod, int next) {
		int d = std::max(0, std::min(x[nod], r[nod][next].pair_capacity - r[nod][next].pair_preflow));
		if (l[nod] == l[next] + 1 && d > 0) {
			r[nod][next].pair_preflow += d;
			r[next][nod].pair_preflow -= d;

			x[nod] -= d;
			x[next] += d;

			enqueue(next);
		}
	}

	void gap(int k) {
		for (int i = 1; i < r.size(); i++) {
			if (l[i] >= k) {
				count[l[i]]--;
				l[i] = std::max(l[i], (int)r.size() - 1);
				count[l[i]]++;
				enqueue(i);
			}
		}
	}

	void enqueue(int nod) {
		if (l[nod] < n && x[nod] > 0 && !active[nod]) {
			active[nod] = true;
			B[l[nod]].push_back(nod);
			b = std::max(b, l[nod]);
		}
	}

	void discharge(int nod) {
		for (auto& e : r[nod]) {
			if (x[nod] > 0) {
				push(nod, e.to);
			}
			else {
				break;
			}
		}

		if (x[nod] > 0) {
			if (count[l[nod]] == 1) {
				gap(l[nod]);
			}
			else {
				relabel(nod);
			}
		}
	}
public:
	int max_flow(graph &g, int source, int dest) {
		r = flow_graph(g.size(), flow_node());
		for (int i = 1; i < g.size(); i++) {
			for (auto it : g[i]) {
				r[i][it.first] = { it.second, 0 };
			}
		}

		l = std::vector<int>(r.size(), 0);
		x = std::vector<int>(r.size(), 0);
		active = std::vector<bool>(r.size(), 0);
		count = std::vector<int>(r.size() + 1, 0);
		B = std::vector<std::vector<int> >(r.size());
		n = r.size() - 1;

		for (auto& it : r[source]) {
			x[source] += it.capacity;
		}

		count[0] = n;
		enqueue(source);
		active[dest] = true;
		

		while (b >= 0) {
			if (!B[b].empty()) {
				int nod = B[b].back();
				B[b].pop_back();
				active[nod] = false;
				discharge(nod);
			}
			else {
				b--;
			}
		}

		return x[dest];
	}

#undef preflow
#undef capacity
};

int main() {
	int n, m, x, y, c;
	std::ifstream cin("maxflow.in");
	std::ofstream cout("maxflow.out");
	cin >> n >> m;
	g = std::vector< graph_node >(n + 1, graph_node());
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> c;
		g[x].push_back({ y, c });
	}


	cout << (new MaxFlow ())->max_flow(g, 1, n);
	

	return 0;
}