#include <cstdio>
#include <vector>

using namespace std;

const int oo = 1<<30;

int N, M;
int C[1001][1001];
int F[1001][1001];
vector<int> G[1001];
int T[1001];

int q[1001];
bool inq[1001];
int bq, eq;
bool viz[1001];
bool bf() {
	int u;

	bq = eq = 0;
	q[eq++] = 1;
	memset(viz, 0, sizeof(viz));
	viz[1] = true;

	while (bq < eq) {
		u = q[bq];
		for (vector<int>::const_iterator v = G[u].begin(); v != G[u].end(); ++v) {
			if (viz[*v] || (C[u][*v] == F[u][*v]))
				continue;
			viz[*v] = true;
			q[eq++] = *v;
			T[*v] = u;
			if (*v == N)
				return true;
		}

		++bq;
	}
	return false;
}

int main(int argc, char *argv[]) {
	int i, u, v, w, n;
	int flow, fmin;

	FILE *fi = fopen("maxflow.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	for (i = 0; i < M; ++i) {
		fscanf(fi, "%d %d %d", &u, &v, &w);
		C[u][v] += w;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	fclose(fi);

	for (flow=0; bf(); flow += fmin) {
		fmin = oo;
		for (n = N; n != 1; n = T[n])
			fmin = min(fmin, C[T[n]][n] - F[T[n]][n]);
		//printf("Ameliorez cu %d: ", fmin);
		for (n = N; n != 1; n = T[n]) {
			//printf("%d <- ", n);
			F[T[n]][n] += fmin;
			F[n][T[n]] += fmin;
		}
		//printf("1\n");
	}

	//printf("%d\n", flow);
	
	FILE *fo = fopen("maxflow.out", "w");
	fprintf(fo, "%d\n", flow);
	fclose(fo);

	return 0;
}