#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define ech(It, A) for (typeof(A.begin()) It = A.begin(); It != A.end(); ++It)

const int inf = 1<<30;
vector< vector<int> > adjl; //have problem if exist multiple edges between two vertices
vector< vector<int> > adjm;

int main() {
	ifstream fin("maxflow.in");
	ofstream fout("maxflow.out");
	int n, m;
	fin >> n >> m;
	adjl.resize(n+1);
	adjm.assign( n+1, vector<int>(n+1) );
	int max_cap = inf;

	for (int u, v, c, i = 0; i < m; ++i) {
		fin >> u >> v >> c;
		adjl[u].push_back(v);
		adjl[v].push_back(u);
		adjm[u][v] = c;
		max_cap = max( max_cap, c );
	}

	int msb = max_cap;
	for (int i = 0; i < 5; ++i) {
		msb |= msb>>(1<<i);
	}
	msb -= msb>>1;
	int flow = 0;

	for (int scale = msb; scale > 0; scale>>=1) {
		while (true) {
			bool reach_sink = false;
			queue<int> Q;
			Q.push(1);
			vector<int> par(n+1);
			vector<bool> visited(n+1);
			visited[1] = true;

			while (!Q.empty()) {
				int u = Q.front();
				Q.pop();
				ech( it, adjl[u] ) {
					if (!visited[*it] && adjm[u][*it] >= scale) {
						Q.push(*it);
						par[*it] = u;
						visited[*it] = true;
						if (*it == n) {
							reach_sink = true;
							break;
						}
					}
				}
				if (reach_sink) break;
			}
			if (!reach_sink) break;

			int cap = inf;
			for (int v = n; v != 1; v = par[v]) {
				cap = min( cap, adjm[par[v]][v] );
			}
			for (int v = n; v != 1; v = par[v]) {
				adjm[par[v]][v] -= cap;
				adjm[v][par[v]] += cap;
			}
			flow += cap;
		}
	}

	fout << flow;
	return 0;
}