#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

#define MaxN 20
#define Inf 1234567

using namespace std;

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

int N, M, flow, nod, node;
int TT[MaxN], C[MaxN][MaxN], F[MaxN][MaxN];
vector<int> G[MaxN];
queue<int> q;
vector<bool> visited;

int BFSRoadExists() {
	queue<int> newQueue;
	q.swap(newQueue);

	q.push(1);

	vector<bool> unvisitedVector(MaxN, false);
	visited.swap(unvisitedVector);
	visited[1] = true;

	while (!q.empty()) {
		int n = q.front();
		q.pop();

		for (int i = 0; i < G[n].size(); ++i) {
			int next = G[n][i];

			if (C[n][next] == F[n][next] || visited[next])
				continue;

			TT[next] = n;
			visited[next] = true;
	
			if (next == N)
				return 1;

			q.push(next);
		}
	}

	return 0;
}

int main() {
	fin >> N >> M;

	for (int i = 0; i < M; ++i) {
		int x, y, cost;
		fin >> x >> y >> cost;
		++x; ++y;	
		C[x][y] = cost;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	while (BFSRoadExists()) {
		int fmin = Inf;
		
		for (nod = N; TT[nod] != 0; nod = TT[nod]) {
			fmin = min(fmin, C[TT[nod]][nod] - F[TT[nod]][nod]);
		}

		for (nod = N; TT[nod] != 0; nod = TT[nod]) {
			F[TT[nod]][nod] += fmin;
			F[nod][TT[nod]] -= fmin;
		}

		flow += fmin;
	}

	fout << flow << '\n';

	return 0;
}