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

#define min(x,y) ((x < y) ? x : y)
#define max(x,y) ((x > y) ? x : y)
#define c(x,y) C[x][y]
#define f(x,y) F[x][y]
#define oo (1 << 30)
#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;

void 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)
			if (viz[g[x][i]] != vizit) {
				if (c (x, g[x][i]) - f(x, g[x][i]) > 0) {
					Q.push (g[x][i]);
					t[g[x][i]] = x;
					viz[g[x][i]] = vizit;
				}
				else
					if (f(g[x][i], x) > 0) {
						Q.push (g[x][i]);
						t[g[x][i]] = -x;
						viz[g[x][i]] = vizit;
					}
			}
	}
}
				
		

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();
	do {
		++vizit;
		bfs();
		if (viz[n] < vizit) // Iesirea retelei nu a fost marcata
			break;
		int x = n, MIN = oo;
		while (t[x]) {
			if (t[x] > 0)
				MIN = min (MIN, c(t[x], x) - f(t[x], x));
			else
				MIN = min (MIN, f(x, -t[x]));
				x = max (-t[x], t[x]);
		}
		sol += MIN;
		x = n;
		while (t[x]) {
			if (t[x] > 0)
				f(t[x], x) += MIN;
			else
				f(x, -t[x]) -= MIN;
			x = max (t[x], -t[x]);
		}
	} while (1);
	fout << sol;
	fout.close();
	return 0;
}