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

using namespace std;

fstream fin("maxflow.in", ios::in);
fstream fout("maxflow.out", ios::out);

#define MAXN 1001
int N, M, flow;
pair <int, pair<int, bool>> parents[MAXN];
pair <int, int> network[MAXN][MAXN];

void read()
{
	fin >> N >> M;
	for (int i = 1, x, y, c; i <= M; i++)
		fin >> x >> y >> c,
		network[x][y].second = c;
	fin.close();
}
int find_path(int node)
{
	queue <int> q;
	bool used[MAXN];
	memset(used + 1, 0, sizeof(bool) * N);
	q.push(node);
	used[node] = 1;
	parents[node].second.first = ~(1 << 31);

	while (!q.empty()){
		if (q.front() == N) return 1;
		int res_cap;
		for (int i = 1; i <= N; i++){
			res_cap = network[q.front()][i].second - network[q.front()][i].first;
			if ((res_cap > 0 || network[i][q.front()].first) && !used[i])
				q.push(i),
				parents[i].first = q.front(),
				parents[i].second.first = min(!res_cap ? network[i][q.front()].first : parents[q.front()].second.first,
											  !res_cap ? network[i][q.front()].first : res_cap),
				parents[i].second.second = !res_cap ? false : true,
				used[i] = true;
		}
		q.pop();
	}
	return 0;
}
int main()
{
	read();
	while (true){
		bool found = find_path(1);
		if (!found) break;
		
		int node = N;
		while (node){
			bool edge = parents[node].second.second;
			int sc = node, fs = parents[node].first;
			if (!edge)  swap(fs, sc);
			if (edge)  network[fs][sc].first += parents[N].second.first;
			else network[fs][sc].first -= parents[N].second.first;
			node = parents[node].first;
		}
		flow += parents[N].second.first;
	}

	fout << flow << "\n";
	fout.close();
	return 0;
}