#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int N, M, flow, cost[1010][1010], flux[1010][1010], ant[1010];
vector<int> A[1010];
queue<int> Q;

int BFS() {
	Q.push(1);
	memset(ant, 0, sizeof(ant));
	ant[1] = 1;
	for (; !Q.empty(); Q.pop()) {
		int number = Q.front();
		for (vector<int>::iterator it = A[number].begin(); it != A[number].end(); it++) {
			if (flux[number][*it] < cost[number][*it] && !ant[*it]) {
				ant[*it] = number;
				Q.push(*it);
			}
		}
	}
	return ant[N];
}

int main() {	
	fin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int x, y, z;
		fin >> x >> y >> z;
		A[x].push_back(y);
		A[y].push_back(x);
		cost[x][y] += z;		
	}
	for (; BFS(); ) {
		for (vector<int>::iterator it = A[N].begin(); it != A[N].end(); it++) {
			if (cost[*it][N] > flux[*it][N] && ant[*it]) {
				int number, minflow = cost[*it][N] - flux[*it][N];
				for (number = *it; number > 1; minflow = min(minflow, cost[ant[number]][number] - flux[ant[number]][number]), number = ant[number]);
				flux[*it][N] += minflow; flux[N][*it] -= minflow;
				for (number = *it; number > 1; flux[ant[number]][number] += minflow, flux[number][ant[number]] -= minflow, number = ant[number]);
				flow += minflow;
			}
		}
	}
	fout << flow << '\n';
	fout.close();
	return 0;
}