#include <vector>
#include <string>
#include <fstream>
#include <iostream>
#include <algorithm>

using std::vector;
using std::string;

#define oo 0x3f3f3f3f

class Node {
private:
	int e;
	int h;

public:
	Node(const int& e, const int& h) : e{ e }, h{ h }{};
	Node() : e{ 0 }, h{ 0 }{};

	friend class Pompare;
};

class Pompare {
private:
	string input_file;
	string output_file;
	int **C, **F, n;
	int source, destination;
	vector<std::pair<int, bool>>* graf;
	vector<Node> noduri;

	void read() {
		std::ifstream in{ input_file, std::ios::in };

		int m, x, y;
		in >> n >> m;

		graf = new vector<std::pair<int, bool>>[n + 1];
		noduri.resize(n + 1);

		source = 1, destination = n;

		C = new int* [n + 1];
		for (int i = 1; i <= n; ++i) {
			C[i] = new int[n + 1];
		}
		F = new int* [n + 1];
		for (int i = 1; i <= n; ++i) {
			F[i] = new int[n + 1];
		}

		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				C[i][j] = F[i][j] = 0;
			}
		}

		for (int i = 1; i <= m; ++i) {
			in >> x >> y;
			in >> C[x][y];
			graf[x].push_back(std::make_pair(y, true));
			graf[y].push_back(std::make_pair(x, false));
		}

		in.close();
	}

	void initializare() {
		noduri[source].h = n;
		for (const auto& vecin : graf[source]) {
			if (vecin.second) {
				F[source][vecin.first] += C[source][vecin.first];
				C[vecin.first][source] += C[source][vecin.first];
				
				noduri[source].e -= C[source][vecin.first];
				noduri[vecin.first].e += C[source][vecin.first];

				C[source][vecin.first] = 0;
			}
		}
	}

	void pompare(int u, int v) {
		int fmin = std::min(C[u][v], noduri[u].e);

		if (std::find(graf[u].begin(), graf[u].end(), std::make_pair(v, true)) != graf[u].end()) {
			F[u][v] += fmin;
			C[u][v] -= fmin;
			C[v][u] += fmin;
		}
		else {
			F[v][u] -= fmin;
			C[v][u] += fmin;
			C[u][v] -= fmin;
		}

		noduri[u].e -= fmin;
		noduri[v].e += fmin;
	}

	void inaltare(int u) {
		int min_h = oo;

		for (const auto& vecin : graf[u]) {
			if (C[u][vecin.first] > 0) {
				min_h = std::min(min_h, noduri[u].h);
			}
		}

		if (min_h == oo || noduri[u].h > min_h) {
			return;
		}

		noduri[u].h = 1 + min_h;
	}

	void descarca(int u) {
		auto curr = graf[u].begin();
		
		while (noduri[u].e > 0) {

			if (curr == graf[u].end()) {
				inaltare(u);
				curr = graf[u].begin();
			}
			else if (C[u][curr->first] > 0 && noduri[u].h == noduri[curr->first].h + 1) {
				pompare(u, curr->first);
			}
			else {
				curr++;
			}
		}
	}
	
	void solve() {
		

		vector<int> list;
		for (int i = 1; i <= n; ++i) {
			if (i != source && i != destination) {
				list.push_back(i);
			}
		}

		while (!list.empty()) {
			int u = *list.begin();
			list.erase(list.begin());

			int old_h = noduri[u].h;
			descarca(u);
			if (noduri[u].h != old_h) {
				list.push_back(u);
			}
		}
	}

public:
	Pompare(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{
		read();
		initializare();
		while (1) {
			int flag = 0;
			for (int i = 2; i < n; ++i) {
				if (noduri[i].e) {	
					flag = 1;
					break;
				}
			}
			if (!flag) {
				break;
			}
			solve();
		}

	};

	void print() {
		std::ofstream out{ output_file, std::ios::trunc };

		out << noduri[destination].e << '\n';

		out.close();
	}
};

int main(int argc, char** argv) {
	Pompare p{ "maxflow.in", "maxflow.out" };
	p.print();


	return 0;
}