#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

int main() {
#ifdef INFOARENA
	freopen("maxflow.in", "r", stdin);
	freopen("maxflow.out", "w", stdout);
#endif
	cin.sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adjl(n);
	vector<vector<int>> C(n, vector<int>(n, 0));
	for (int i = 0; i < m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		u--, v--;
		if (C[u][v] == 0 && C[v][u] == 0) {
			adjl[u].push_back(v);
			adjl[v].push_back(u);
		}
		C[u][v] += c;
	}
	int s = 0, t = n-1;
	vector<int> e(n, 0);
	for (int v: adjl[s]) {
		e[s] -= e[v] = C[v][s] = C[s][v];
		C[s][v] = 0;
	}
	vector<int> d(n, n);
	d[t] = 0;
	vector<int> cntd;
	vector<queue<int>> V;
	int k;
	function<void()> cmpd = [&] () {
		queue<int> q;
		q.push(t);
		vector<int> vis(n, false);
		vis[t] = true;
		do {
			int v = q.front();
			q.pop();
			for (int u: adjl[v]) if (!vis[u] && C[u][v] > 0) {
				vis[u] = true;
				d[u] = d[v]+1;
				q.push(u);
			}
		} while (!q.empty());
		// q.push(s);
		// vis[s] = true;
		// do {
		// 	int v = q.front();
		// 	q.pop();
		// 	for (int u: adjl[v]) if (!vis[u] && C[u][v] > 0) {
		// 		vis[u] = true;
		// 		d[u] = d[v]+1;
		// 		q.push(u);
		// 	}
		// } while (!q.empty());
		cntd.assign(2*n, 0);
		V.assign(2*n, queue<int>());
		k = 0;
		for (int u = 0; u < n; u++) {
			cntd[d[u]]++;
			if (e[u] > 0) {
				V[d[u]].push(u);
				k = max(k, d[u]);
			}
		}
	};
	vector<vector<int>::iterator> cur(n);
	for (int u = 0; u < n; u++) {
		cur[u] = adjl[u].begin();
	}
	// int cnt = 0, cnt1 = 0;
	int cntrelabel = n;
	do {
		if (cntrelabel == n) {
			cntrelabel = 0;
			cmpd();
			// for (int u = 0; u < n; u++) printf("%d%c", d[u], " \n"[u == n-1]);
		}
		int u = V[k].front();
		// printf("%d %d %d\n", u, d[u], e[u]);
		for (; e[u] > 0 && cur[u] != adjl[u].end(); ++cur[u]) {
			int v = *cur[u];
			// cnt++;
			if (C[u][v] == 0 || d[u] <= d[v]) continue;
			// printf("%d\n", *cur[u]);
			// cnt1++;
			int f = min(e[u], C[u][v]);
			e[u] -= f;
			C[u][v] -= f;
			C[v][u] += f;
			if (e[v] == 0) V[d[v]].push(v);
			e[v] += f;
		}
		V[k].pop();
		if (cur[u] == adjl[u].end()) cur[u] = adjl[u].begin();
		if (e[u] > 0) {
			while (C[u][*cur[u]] == 0) ++cur[u];
			for (auto it = cur[u]; it != adjl[u].end(); ++it) {
				if (C[u][*it] > 0 && d[*cur[u]] > d[*it]) cur[u] = it;
			}
			d[u] = d[*cur[u]]+1;
			V[d[u]].push(u);
			cntd[k]--;
			cntd[d[u]]++;
			if (k < n-1 && cntd[k] == 0) {
				for (int i = k+1; i < n; i++) V[k] = queue<int>();
				for (int v = 0; v < n; v++) if (d[v] > k && d[v] < n) d[v] = n;
			}
			k = d[u];
			cntrelabel++;
		}
		while (k > 0 && V[k].empty()) k--;
	} while (k > 0);
	// printf("%d %d\n", cnt1, cnt);
	// for (int u = 0; u < n; u++) printf("%d%c", d[u], " \n"[u == n-1]);
	// for (int u = 0; u < n; u++) printf("%d%c", e[u], " \n"[u == n-1]);
	// printf("%d\n", -e[s]);
	printf("%d\n", e[t]);
}