#include <iostream>
#include <fstream>
#include <assert.h>
#include <list>
#include <queue>
#include <bitset>
#include <cstring>

#define min(a,b) ((a)<(b))?(a):(b)
#define forever while(1)

const int NMAX = 1000;
const int MMAX = 5000;

const char IN[] = "maxflow.in", OUT[] = "maxflow.out";

using namespace std;

int N, M;
int G[NMAX][NMAX];
int Gf[NMAX][NMAX];

const int INF = 0x3f3f3f3f;
const int source = 1;
int drain;

inline void read_data()
{
	assert(freopen(IN, "r", stdin));
	assert(scanf("%d %d", &N, &M));
	drain = N;
	for (int i = 0; i < M; ++i) {
		int u, v, c;
		assert(scanf("%d %d %d", &u, &v, &c));
		G[u][v] = c;
		Gf[u][v] = c; 
	}
	fclose(stdin);
}

list<int> find_path()
{
	int PI[NMAX];
	list<int> p;
	queue<int> Q;
	bitset<NMAX> inQ; inQ.reset();
	memset(PI, 0, sizeof(PI));
	Q.push(source);
	inQ[source].flip();
	while (!Q.empty() && !inQ[drain]) {
		int u = Q.front(); Q.pop();
		if (u == drain) break;
		for (int v = 1; v <= N; ++v) {
			if (Gf[u][v] && !inQ[v]) {
				PI[v] = u;
				Q.push(v);
				inQ[v].flip();
				if (v == drain) break;
			}
		}
	}
	if (PI[drain] == 0) return list<int>();
	p.push_back(drain);
	int u = PI[drain];
	int maximum_path_flow = Gf[u][drain];
	while (PI[u] != 0) {
		p.push_front(u);
		maximum_path_flow = min(maximum_path_flow, Gf[PI[u]][u]);
		u = PI[u];
	}
	p.push_front(source);
	p.push_front(maximum_path_flow);
	return p;
}

int saturate_path(list<int> path)
{
	int maximum_path_flow = path.front(); path.pop_front();
	std::list<int>::iterator it = path.begin();
	for (int i = 0; i < path.size() - 1; ++i) {
		int u = *it;
		int v = *(++it);
		Gf[u][v] -= maximum_path_flow;
		Gf[v][u] += maximum_path_flow;
	}
	return maximum_path_flow;
}

int maxflow()
{
	int mflow = 0;
	forever {
		list<int> p = find_path();
		if (p.empty()) break;
		mflow += saturate_path(p);
	}
	return mflow;
}

int main()
{
	read_data();
	fprintf(fopen(OUT, "w"), "%d\n", maxflow());
	return 0;
}