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

#define min(x,y) ((x < y) ? x : y)
#define N 1005
#define add push_back

typedef unsigned u;

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

queue <int> Q;
vector <int> g[N], t(N, 0), viz(N, 0);
int c[N][N], f[N][N], vizit, n, m, sol;

int bfs () {
	Q.push(1);
	viz[1] = vizit;
	while (Q.size()) {
		int x = Q.front();
		Q.pop();
		for (u i = 0; i < g[x].size(); ++i) {
			int y = g[x][i];
			if (f[x][y] < c[x][y] && viz[y] < vizit) {
				Q.push (y);
				t[y] = x;
				viz[y] = vizit;
			}
		}
	}
	return viz[n];
}
				
		

int main() {
	fin >> n >> m;
	while (m--) {
		int x, y, C;
		fin >> x >> y >> C;
		g[x].add(y);
		g[y].add(x);
		c[x][y] = C;
	}
	fin.close();
	while (++vizit == bfs())
		for (int i = 1; i < n; ++i)
			if (f[i][n] < c[i][n]) {
				int MIN = c[i][n] - f[i][n], x = i;
				while (x != 1) {
					MIN = min (c[t[x]][x] - f[t[x]][x], MIN);
					x = t[x];
				}
				sol += MIN;
				f[i][n] += MIN;
				f[n][i] -= MIN;
				x = i;
				while (x != 1) {
					f[t[x]][x] += MIN;
					f[x][t[x]] -= MIN;
					x = t[x];
				}
			}
	fout << sol;
	fout.close();
}