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

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

#define oo 0x3f3f3f3f

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

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

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

		source = 1, destination = n;

		graf = new vector<int>[n + 1];
		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;
			}
		}
		viz = new bool[n + 1];
		t = new 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 = 1; i <= n; ++i) {
			viz[i] = false;
		}
		viz[source] = true;
		queue<int> q;
		q.push(source);

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

			if (front == destination) {
				continue;
			}

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

		return viz[destination];
	}

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

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

				if (!fmin) {
					continue;
				}

				for (int nod = destination; nod != source; 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, std::ios::trunc };

		out << flow << '\n';

		out.close();
	}

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

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

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

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

	return 0;
}