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

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

#define oo 0x3f3f3f3f

class FF {
private:
	string input_file;
	string output_file;
	int n;
	int** C;
	int** F;
	int* t;
	bool* viz;
	vector<int>* graf;
	int flow;

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

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

		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;
			}
		}

		t = new int[n + 1];
		viz = new bool[n + 1];

		graf = new vector<int>[n + 1];

		for (int i = 1; i <= m; ++i) {
			in >> x >> y;
			in >> C[x][y];
			graf[x].push_back(y);
			graf[y].push_back(x);
		}

		in.close();
	}

	bool bfs() {
		for (int i = 0; i <= n; ++i) {
			viz[i] = false;
		}
		queue<int> q;
		q.push(1);
		viz[1] = true;

		while (!q.empty()) {
			int front = q.front();
			q.pop();

			if (front == n) {
				continue;
			}

			for (const auto& vecin : graf[front]) {
				if (viz[vecin] || C[front][vecin] == F[front][vecin]) {
					continue;
				}
				viz[vecin] = true;
				q.push(vecin);
				t[vecin] = front;
			}
		}

		return viz[n];
	}

	void solve() {
		for (; bfs();) {
			for (const auto& vecin : graf[n]) {
				if (!viz[vecin] || C[vecin][n] == F[vecin][n]) {
					continue;
				}

				t[n] = vecin;

				int fmin = oo;
				for (int nod = n; nod != 1; nod = t[nod]) {
					fmin = std::min(fmin, C[t[nod]][nod] - F[t[nod]][nod]);
				}

				if (!fmin) {
					continue;
				}

				for (int nod = n; nod != 1; nod = t[nod]) {
					F[t[nod]][nod] += fmin;
					F[nod][t[nod]] -= fmin;
				}

				flow += fmin;
			}
		}
	}

public:
	FF(const string& input_file, const string& output_file) : input_file{ input_file }, output_file{ output_file }, flow{ 0 }{
		read();
		solve();
	};

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

		out << flow << '\n';

		out.close();
	}

	~FF() {
		delete[] graf;
		delete[] t;
		delete[] viz;

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

		delete[] C;
		delete[] F;
	}
};

int main3(int argc, char** argv) {
	
	FF ff{ "maxflow.in", "maxflow.out" };
	ff.print();

	return 0;
}