#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

const int NMAX = 1010;
const int INF = 1000000000;

vector<vector<int>> c;
vector<vector<int>> flow;
int *currentPathCapacity;
int* parent; // parcurgere inversa 
vector <int> *v;
int V, E;

void allocateMemory(int MAXV) {
	for (int i = 1; i <= MAXV + 5; i++) {
		c.push_back(vector<int>(MAXV + 5, 0));
		flow.push_back(vector<int>(MAXV + 5, 0));
	}
	v = new vector<int>[MAXV + 5];
	parent = new int[MAXV + 5];
	currentPathCapacity = new int[MAXV + 5];
		
}

int BFS() {
	queue <int> q;
	q.push(1);
	memset(parent, -1, (V + 5) * sizeof(int)); // reinitializam lista parcursa cu -1
	parent[1] = -2;
	currentPathCapacity[1] = INF;
	while (!q.empty()) {
		int nod = q.front();
		q.pop();
		for (auto it : v[nod]) {
			if (parent[it] == -1) {
				if (c[nod][it] - flow[nod][it] > 0) {
					parent[it] = nod;
					currentPathCapacity[it] = min(currentPathCapacity[nod], c[nod][it] - flow[nod][it]);
					if (it == V) 
						return currentPathCapacity[it];
					q.push(it);
				}
			}
		}

	}
	return 0; // no more flow to pass :(
}

void updateFlow(int tempFlow) {
	int currentNode = V;
	while (currentNode != 1) {
		int previousNode = parent[currentNode];
		flow[previousNode][currentNode] += tempFlow;
		flow[currentNode][previousNode] -= tempFlow;
		currentNode = previousNode;
	}
}

int edmondsKarp() {
	int maxFlow = 0;
	while (true) {
		int tempFlow = BFS();
		if (!tempFlow)
			break;
		maxFlow += tempFlow;
		updateFlow(tempFlow);
	}
	return maxFlow;
}

void deallocateMemory() {
	delete currentPathCapacity;
	delete parent;
}

int main() {
	FILE* fdescriptor = fopen("maxflow.in", "r");
	fscanf(fdescriptor, "%d", &V);
	fscanf(fdescriptor, "%d", &E);
	allocateMemory(V);
	for (int x, y, cst; E; E--) {
		fscanf(fdescriptor, "%d", &x);
		fscanf(fdescriptor, "%d", &y);
		fscanf(fdescriptor, "%d", &cst);
		c[x][y] = cst;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	fclose(fdescriptor);
	FILE* gdescriptor = fopen("maxflow.out", "w");
	fprintf(gdescriptor, "%d", edmondsKarp());
	fclose(gdescriptor);
	deallocateMemory();
	return 0;
}