#include <string>
#include <vector>
#include <fstream>
#include <set>
#include <iostream>
#include <deque>

using std::set;
using std::vector;
using std::string;
using std::deque;

#define oo 0x3f3f3f3f

class Node {
private:
	int h, e;

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

	friend class Pompare;
};

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

	void read() {
		std::ifstream in(input_file);

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

		source = 1; destination = n;
		noduri.resize(n + 1);

		graf = new vector<std::pair<int, bool>>[n + 1];

		C = new int* [n + 1];
		for (int i = 0; i <= n; ++i) {
			C[i] = new int[n + 1];
			for (int j = 0; j <= n; ++j) {
				C[i][j] = 0;
			}
		}
		F = new int* [n + 1];
		for (int i = 0; i <= n; ++i) {
			F[i] = new int[n + 1];
			for (int j = 0; j <= n; ++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() {
		for (int i = 1; i <= n; ++i) {
			noduri[i] = Node(0, 0);
		}
		noduri[source].h = n;

		for (const auto& vecin : graf[source]) {
			F[source][vecin.first] = C[source][vecin.first];
			C[source][vecin.first] = 0;
			C[vecin.first][source] = F[source][vecin.first];

			noduri[vecin.first].e = F[source][vecin.first];
			noduri[source].e -= F[source][vecin.first];
		}
	}

	void pompare(int u, int v) {
		if (u == source || u == destination || noduri[u].e <= 0 || C[u][v] <= 0 || noduri[u].h != noduri[v].h + 1) {
			return;
		}

		int fmin = std::min(noduri[u].e, C[u][v]);
		if (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[u][v] -= fmin;
			C[u][v] += fmin;
			C[v][u] += fmin;
		}

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

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

		for (auto& vecin : graf[u]) {
			minim_h = std::min(minim_h, noduri[vecin.first].h);
		}

		if (noduri[u].h > minim_h) {
			return;
		}

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

	void descarca(int u) {
		auto curr = graf[u].begin();
		while (noduri[u].e > 0) {
			if (noduri[u].h == n + 1) {
				return;
			}

			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() {
		initializare();

		vector<int> list;
		for (int i = 1; i <= n; ++i) {
			if (i != source && i != destination) {
				list.push_back(i);
			}
		}
		
		while (!list.empty()) {
			auto first = *list.begin();
			list.erase(list.begin());

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

public:
	Pompare(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }{
		read();
		solve();
	};

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

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

		out.close();
	}

	~Pompare() {
		delete[] graf;
	}
};

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

	return 0;
}