#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
int n, m, res;
int c[MAXN][MAXN], f[MAXN][MAXN];
int d[MAXN]; bool vis[MAXN];
vector<int> r; queue<int> q;

void read() {
	fin >> n >> m;
	for (int i = 1, x, y, f; i <= m; ++i) {
		fin >> x >> y >> f;
		c[x][y] += f;
	}
	fin.close();
}

bool bfs() {
	for (int i = 1; i <= n; ++i) {
		vis[i] = false;
		d[i] = 0;
	}
	q.push(1); vis[1] = true;
	for (; !q.empty(); q.pop()) {
		int node = q.front();
		if (f[node][n] < c[node][n]) {
			r.push_back(node);
			continue;
		}
		for (int next = 1; next <= n; ++next)
			if (!vis[next])
				if (f[node][next] < c[node][next]) {
					d[next] = node; vis[next] = true;
					q.push(next);
				}
	}
	if (!r.empty())
		return true;
	return false;
}

void relax() {
	for (; !r.empty(); r.pop_back()) {
		int node = r.back();
		int maxflow = c[node][n] - f[node][n];
		while (node != 1) {
			int prev = d[node];
			maxflow = min(maxflow, c[prev][node] - f[prev][node]);
			node = prev;
		}
		node = r.back();
		f[node][n] += maxflow;
		f[n][node] -= maxflow;
		while (node != 1) {
			int prev = d[node];
			f[prev][node] += maxflow;
			f[node][prev] -= maxflow;
			node = prev;
		}
		res += maxflow;
	}
}

void solve() {
	while (bfs())
		relax();
}

void write() {
	fout << res << '\n';
	fout.close();
}

int main() {
	read();
	solve();
	write();
}