#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>

//#define DEBUG
#define INFINITY 12345

using namespace std;

int BFS(const vector< vector<int> > neighbour_lists,
		int **capacity, int **flow, vector<int> &parent,
		int source, int sink)
{
	vector<int> path_capacity(neighbour_lists.size());
	queue<int> node_queue;
	unsigned long source_idx = (unsigned long) source;
	int residual_capacity;

	fill(parent.begin(), parent.end(), -1);
	parent[source_idx] = -2;

	path_capacity[source_idx] = INFINITY;
	node_queue.push(source);

	while (!node_queue.empty()) {
		int u = node_queue.front();
		unsigned long u_idx = (unsigned long) u;
		node_queue.pop();

		const vector<int> &n_list = neighbour_lists[u_idx];
		for (vector<int>::const_iterator it = n_list.begin(); it != n_list.end(); ++it) {
			int v = *it;
			unsigned long v_idx = (unsigned long) v;

			if (capacity[u_idx][v_idx] > flow[u_idx][v_idx] && parent[v_idx] == -1) {
				parent[v_idx] = u;
				residual_capacity = capacity[u_idx][v_idx] - flow[u_idx][v_idx];
				path_capacity[v_idx] = min(path_capacity[u_idx], residual_capacity);
				if(v == sink) {
					return path_capacity[v_idx];
				} else {
					node_queue.push(v);
				}
			}
		}
	}
	
	return 0;
}

void EdmondsKarp(const vector< vector<int> > neighbour_lists, int n,
			int **capacity,
			int source, int sink) {
	int **flow;
	size_t n_size = (size_t) n;
	vector<int> parent(n_size);
	int max_flow, saturate;
	int i, u, v;

	flow = new int*[n_size];
	for(i = 0; i < n; i++)
		flow[i] = (int*) calloc(n_size, sizeof(int));

	max_flow = 0;

	for (;;) {
		saturate = BFS(neighbour_lists, capacity, flow, parent, source, sink);
		if (saturate == 0)
			break;

		max_flow += saturate;
		v = sink;
		while (v != source) {
			u = parent[v];
			flow[u][v] += saturate;
			flow[v][u] -= saturate;
			v = u;
		}
	}

	FILE *f = fopen("maxflow.out", "wt");
	if (f != NULL) {
		fprintf(f, "%d\n", max_flow);
		fclose(f);
	}
}

int main() {
	FILE *f;
	int **capacity;
	int source, sink;
	int n, m;
	int u, v;

	f = fopen("maxflow.in", "rt");
	if (f == NULL) {
		fprintf(stderr, "Fiserul retea.in n-a putut fi deschis.\n");
		exit(-1);
	}

	if (fscanf(f, "%d", &n) != 1)
		exit(-1);
	if (fscanf(f, "%d", &m) != 1)
		exit(-1);

	capacity = new int*[n];
	for (int i = 0; i < n; i++) {
		capacity[i] = new int[n];
		fill(capacity[i], capacity[i] + n, 0);
	}

	vector< vector<int> > neighbour_lists(n);

	for (int i = 0; i < m; i++) {
		if (fscanf(f, "%d", &u) != 1)
			exit(-1);
		if (fscanf(f, "%d", &v) != 1)
			exit(-1);
		--u;
		--v;
		neighbour_lists[u].push_back(v);
		neighbour_lists[v].push_back(u);
		if (fscanf(f, "%d", &capacity[u][v]) == 0)
			exit(-1);
	}

	source = 0;
	sink = n - 1;

	#ifdef DEBUG

		fprintf(stderr, "debug: neighbour lists for all of the vertices\n");
		for (vector< vector<int> >::iterator v_it = neighbour_lists.begin();
				v_it != neighbour_lists.end(); ++v_it) {
			const vector<int> &n_list = *v_it;
			fprintf(stderr, "[");
			for (vector<int>::const_iterator it = n_list.begin(); it != n_list.end(); ++it)
				fprintf(stderr, " %d", *it);
			fprintf(stderr, " ]\n");
		}

		fprintf(stderr, "debug: capacity matrix\n");

		for (int i = 0; i < n; i++) {
			fprintf(stderr, "| ");
			for (int j = 0; j < n; j++)
				fprintf(stderr, "%d ", capacity[i][j]);
			fprintf(stderr, "|\n");
		}

	#endif

	EdmondsKarp(neighbour_lists, n, capacity, source, sink);

	// Ies de tot
	return 0;
}