#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");

vector<int>ls[1001], ls1[1001];
int c[1001][1001], f[1001][1001];
int fluxin[1001], fluxout[1001];
int viz[1001], tata[1001],n,m;
vector<pair<int, int>>muchii, arce_directe;

int bfs_lant(int s, int t) {
	queue<pair<int, int>>q;
	memset(tata, 0, sizeof tata);
	q.push({ 1,9999999 });
	tata[1] = -1;
	while (!q.empty()) {
		int x = q.front().first;
		int flux = q.front().second;
		for (auto y : ls[x]) {
			if (tata[y] == 0 && (c[x][y] - f[x][y]) > 0) {
				tata[y] = x;
				int flux_nou = min(flux, c[x][y] - f[x][y]);
				if (y == n) {
					return flux_nou;
				}
				q.push({ y,flux_nou });
			}
		}
		q.pop();
	}
	return -1;
}

int bfs(int s) {
	memset(tata, 0, sizeof tata);
	tata[s] = -1;
	int capac = 0;
	queue<int>q;
	q.push(s);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto y : ls1[x]) {
			if (tata[y] == 0) {
				if (c[x][y] - f[x][y] > 0) {
					q.push(y);
					tata[y] = x;
				}
				else {
					arce_directe.push_back({ x,y });
					capac += c[x][y];
				}
			}
		}
	}
	return capac;
}

int edmondsKarp(int s, int t) {
	int total = 0;
	while (true) {
		int flux_nou = bfs_lant(s, t);
		if (flux_nou == -1)
			break;
		total += flux_nou;
		int nod = n;
		while (nod != 1) {

			f[nod][tata[nod]] -= flux_nou;
			f[tata[nod]][nod] += flux_nou;
			nod = tata[nod];
		}
	}
	return total;
}

int main() {
	int  s, t;
	in >> n;
	
	in >> m;
	s = 1;
	t = n;
	while (m--) {
		int a, b, capacitate, flux = 0;
		in >> a >> b >> capacitate;
		ls[a].push_back(b);
		ls1[a].push_back(b);
		ls[b].push_back(a);
		c[a][b] = capacitate;
		c[b][a] = capacitate;
		f[a][b] = flux;
		muchii.push_back({ a,b });
		f[b][a] = capacitate - flux;
		fluxin[b] += flux;
		fluxout[a] += flux;
	}


	out << edmondsKarp(1, n) + fluxin[t];

}