#include <bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
struct edge {
	long long a;
	long long b;
	long long flow;
	long long cap;
};
struct Dinic {
	vector<edge> edges;
	vector<vector<long long>> g;
	vector<long long> level, next;
	long long s, t;
	void build(long long n, long long _s, long long _t) {
		s = _s;
		t = _t;
		level.resize(n + 1), next.resize(n + 1), g.resize(n + 1);
	}
	void add_edge(long long a, long long b, long long cost) {
		long long m = edges.size();
		edges.push_back({ a,b,0,cost });
		edges.push_back({ b,a,0,0 });
		g[a].push_back(m);
		g[b].push_back(m + 1);
	}
	bool bfs() {
		queue<long long> q;
		level[s] = 0;
		q.push(s);
		while (!q.empty()) {
			long long qui = q.front();
			q.pop();
			for (auto i : g[qui]) {
				edge x = edges[i];
				if (x.cap - x.flow < 1 || level[x.b] != -1) {
					continue;
				}
				level[x.b] = level[qui] + 1;
				q.push(x.b);
			}
		}
		return level[t] != -1;
	}
	long long dfs(long long node, long long push) {
		if (push == 0) {
			return 0;
		}
		if (node == t) {
			return push;
		}
		for (long long& i = next[node]; i < (long long)g[node].size(); ++i) {
			edge x = edges[g[node][i]];
			if (x.cap - x.flow < 1 || level[x.b] != level[node] + 1) {
				continue;
			}
			long long flow = dfs(x.b, min(push, x.cap - x.flow));
			if (flow == 0) {
				continue;
			}
			edges[g[node][i]].flow += flow;
			edges[g[node][i] ^ 1].flow -= flow;
			return flow;
		}
		return 0;
	}
	long long flow() {
		long long ans = 0;
		while (true) {
			fill(level.begin(), level.end(), -1);
			if (!bfs()) break;
			fill(next.begin(), next.end(), 0);
			while (long long add = dfs(s, 1e18)) {
				ans += add;
			}
		}
		return ans;
	}
};
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	long long n, m;
	fin >> n >> m;
	Dinic G;
	G.build(n, 1, n);
	for (long long i = 1; i <= m; ++i) {
		long long a, b, cost;
		fin >> a >> b >> cost;
		G.add_edge(a, b, cost);
	}
	fout << G.flow();
}