#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>

#define INFL "maxflow.in"
#define OUTFL "maxflow.out"

using namespace std;

#define nmax 1001

int C[nmax][nmax], Cf[nmax][nmax], F[nmax][nmax], e[nmax], h[nmax];
int inq[nmax];
int n, m;

vector<int> LA[nmax];

void read() {
	scanf("%d%d", &n, &m);

	int a, b, c;
	for(int i=1; i<=m; ++i) {
		scanf("%d%d%d", &a, &b, &c);

		LA[a].push_back(b);
		//LA[b].push_back(a);
		C[a][b] = c;
		Cf[a][b] = c;
	}
}

void init_preflow() {
	h[1] = n;
	
	for(int i=0; i<LA[1].size(); ++i) {
		int u = LA[1][i];
		
		F[1][u] = C[1][u];
		F[u][1] = -F[1][u];

		e[u] = C[1][u];
		e[1] -= C[1][u];

		Cf[1][u] = C[1][u] - F[1][u];
		Cf[u][1] = C[u][1] - F[u][1];
	}
}

void push(int u, int v) {
	int flow = min(e[u], Cf[u][v]);

	F[u][v] += flow;
	F[v][u] = -F[u][v];

	e[u] -= flow;
	e[v] += flow;

	Cf[u][v] = C[u][v] - F[u][v];
	Cf[v][u] = C[v][u] - F[v][u];
}

void solve() {
	init_preflow();

	queue<int> q;
	int u, v, mi;

	for(int i=0; i<LA[1].size(); ++i) {
		u = LA[1][i];
		
		if(u != n) {
			q.push(u);
			inq[u] = 1;
		}
	}

	//printf("Here 1\n");

	while(!q.empty()) {
		u = q.front();
		mi = -1;

		//printf("Here 2 - %d %d\n", u, h[u]);

		for(int i=0; i < LA[u].size() && e[u] > 0; ++i) {
			v = LA[u][i];

			if(Cf[u][v] > 0) {
				if(h[u] > h[v]) {
					push(u, v);

					//printf("Push %d %d\n", u, v);

					if(!inq[v] && v != 1 && v != n) {
						inq[v] = 1;
						q.push(v);
					}
				}
				else if(mi == -1) 
					mi = h[v];
				else 
					mi = min(mi, h[v]);
			}
		}

		if(e[u] != 0) 
			h[u] = 1 + mi;
		else {
			inq[u] = 0;
			q.pop();
		}
	}

	printf("%d\n", e[n]);
}

int main() {
//#define ONLINE_JUDGE 1
#ifndef ONLINE_JUDGE
	freopen(INFL, "r", stdin);
	freopen(OUTFL, "w", stdout);
#endif

	read();
	solve();
	
	return 0;
}