#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <cassert>

using namespace std;

class MaxFlowGraph {
	int N, S, T;
	const int INF;
	int **f, **c;
	int *e, *h;
	void push(int a, int b) {
		assert(h[a] == h[b] + 1 && e[a] > 0 && c[a][b] > f[a][b]);
		int delta = min(e[a], c[a][b] - f[a][b]);
		f[a][b] += delta;
		f[b][a] -= delta;
		e[a] -= delta;
		e[b] += delta;
	}

	bool relabel(int a) {
		assert(e[a] > 0);
		int new_h = 2 * N;
		for (int i = 0; i < N; i++)
			if (f[a][i] < c[a][i])
				new_h = min(new_h, h[i] + 1);
		if (new_h == 2 * N)
			return false;
		h[a] = new_h;
		return true;
	}

public:
	MaxFlowGraph(int N, int S, int T) : N(N), S(S), T(T), INF(2100000000) {
		f = new int*[N];
		c = new int*[N];
		e = new int[N];
		h = new int[N];

		for (int i = 0; i < N; i++) {
			f[i] = new int[N];
			c[i] = new int[N];
		}
		reset();
	}

	~MaxFlowGraph() {
		for (int i = 0; i < N; i++) {
			delete[] f[i];
			delete[] c[i];
		}
		delete[] f;
		delete[] c;
		delete[] e;
		delete[] h;
	}

	void reset() {
		for (int i = 0; i < N; i++) {
			memset(c[i], 0, N * sizeof(int));
		}
	}

	void add_edge(int a, int b, int cap) {
		c[a][b] = cap;
	}

	int maxFlow() {
		memset(e, 0, N * sizeof(int));
		memset(h, 0, N * sizeof(int));
		for (int i = 0; i < N; i++) {
			memset(f[i], 0, N * sizeof(int));
		}
		e[S] = INF;
		h[S] = N;
		queue<int> active;
		vector<bool> seen(N);
		for (int i = 0; i < N; i++)
			if (f[S][i] < c[S][i]) {
				f[S][i] += c[S][i];
				f[i][S] -= c[S][i];
				e[i] += c[S][i];
				active.push(i);
				seen[i] = true;
			}
		while (!active.empty()) {
			int x = active.front();
			while (e[x] > 0) {
				int i = 0;
				for (i = 0; e[x] > 0 && i < N; i++)
					if (f[x][i] < c[x][i] && h[x] == h[i] + 1) { // admissible
							push(x, i);
							if (i != T && !seen[i]) {
								seen[i] = true;
								active.push(i);
							}
					}
				if (e[x] > 0) {
					assert(i == N);
					if (!relabel(x))
						break;
				}
			}
			seen[x] = false;
			active.pop();
		}
		return e[T];
	}
};

int main() {
	freopen("maxflow.in", "r", stdin);
	freopen("maxflow.out", "w", stdout);
	int N, M;
	scanf("%d %d", &N, &M);
	MaxFlowGraph G(N, 0, N - 1);
	for (; M--; ) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		a--, b--;
		G.add_edge(a, b, c);
	}
	printf("%d\n", G.maxFlow());
	
	return 0;
}