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

vector<int>ls[101],ls1[101];
int c[101][101], f[101][101];
int fluxin[101], fluxout[101];
int viz[101],tata[101];
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({ s,9999999 });
	tata[s] = -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 == t) {
					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 = t;
		while (nod != s) {
			
			f[nod][tata[nod]] -= flux_nou;
			f[tata[nod]][nod] += flux_nou;
			nod = tata[nod];
		}
	}
	return total;
}

int main() {
	int n, s, t;
	in >> n;
	int m;
	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(s, t)+fluxin[t];
	
}