#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <algorithm>
using namespace std;
const long inf = 1e9;
struct ver {
	long pr, potok;
	bool obr, use;
};
struct line {
	long from;
	bool obr;
};
int main() {
	long n, a, b, c, v1 = 1, m;
	cin >> n >> m;
	n++;
	vector<vector<ver> > g(n, vector<ver>(n, {0, 0, false, false}));
	for (long i = 0; i < m; i++) {
		cin >> a >> b >> c;
		g[a][b] = { c, 0, false, true};
		g[b][a] = { c, 0, true, true};
	}
	bool out = false;
	while (!out) {
		out = true;
		long minp = inf;
		vector<long> d(n, inf);
		d[1] = 0;
		vector<long> id(n, 0);
		deque<int> q;
		q.push_back(v1);
		vector<line> p(n, { -1, false });
		while (!q.empty())
		{
			int v = q.front();
			q.pop_front();
			id[v] = 1;
			for (long i = 1; i < g[v].size(); ++i)
			{
				long to = i, len = g[v][i].potok, pr = g[v][i].pr;
				if (len != pr && g[v][i].use) {
					out = false;
					if (d[to] > d[v] + len)
					{
						if (g[v][i].obr) {
							p[to] = { v, true };
						}
						else {
							p[to] = { v, false };
						}
						d[to] = d[v] + len;
						if (id[to] == 0)
							q.push_back(to);
						else if (id[to] == 1)
							q.push_front(to);
						id[to] = 1;
					}
				}
			}
		}
		long i = n - 1;
		while (p[i].from != -1) {
			long from = p[i].from;
			bool obr = p[i].obr;
			if (obr)
				minp = min(minp, g[from][i].potok);
			else
				minp = min(minp, g[from][i].pr- g[from][i].potok);
			i = from;
		}
		i = n - 1;
		while (p[i].from != -1) {
			long from = p[i].from;
			bool obr = p[i].obr;
			if (obr) {
				g[from][i].potok -= minp;
				g[i][from].potok += minp;
			}
			else {
				g[from][i].potok += minp;
				g[i][from].potok += minp;
			}
			i = from;
		}
	}
	long potok = 0;
	for (long i = 1; i < g[n - 1].size(); i++) {
		if (g[n - 1][i].obr)
			potok += g[n - 1][i].potok;

	}
	cout << potok;
	return 0;
}