#include <cstdio>
#include <climits>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

#ifdef INFOARENA
#define ProblemName "maxflow"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
typedef long long LL;

#define MAXN 1100
typedef vector< vector<int> > graph;
graph G, GL;
int N;
int C[MAXN][MAXN], F[MAXN][MAXN];
bool viz[MAXN];
int parent[MAXN], dst[MAXN];
#define INFINIT 0x3F3F3F3F

queue<int> Q;
void BFS(int s, graph &g) {
	memset(dst, 0x3F, sizeof(dst));
	memset(parent, 0xFF, sizeof(parent));
	dst[s] = 0;
	parent[s] = -1;
	while (!Q.empty()) Q.pop();
	Q.push(s);
	while (!Q.empty()) {
		int t = Q.front();
		Q.pop();
		for (const auto &u : g[t]) {
			if (F[t][u] >= C[t][u]) continue;
			if (dst[u] != INFINIT) continue;
			dst[u] = dst[t] + 1;
			parent[u] = t;
			Q.push(u);
		}
	}
}

bool buildGL() {
	BFS(0, G);
	if (dst[N - 1] == INFINIT)
		return false;
	for (int u = 0; u < N; ++u) {
		GL[u].clear();
		for (const auto &v : G[u]) {
			if (F[u][v] >= C[u][v]) continue;
			if (dst[v] == dst[u] + 1)
				GL[u].push_back(v);
		}
	}
	return true;
}

int getMinFlow(int nod) {
	int flow = INFINIT;
	while (parent[nod] >= 0) {
		flow = min(flow, C[parent[nod]][nod] - F[parent[nod]][nod]);
		nod = parent[nod];
	}
	return flow;
}

void sendFlow(int nod, int flow) {
	while (parent[nod] >= 0) {
		F[parent[nod]][nod] += flow;
		F[nod][parent[nod]] -= flow;
		nod = parent[nod];
	}
}

int blockingFlow() {
	int flow = 0;
	while (1) {
		BFS(0, GL);
		int sendableFlow = getMinFlow(N - 1);
		if (sendableFlow == INFINIT)
			break;
		flow += sendableFlow;
		sendFlow(N - 1, sendableFlow);
	}
	return flow;
}

int Dinic() {
	GL.resize(N);
	int flow = 0;
	while (buildGL())
		flow += blockingFlow();
	return flow;
}

void input() {
	int M;
	scanf("%d%d", &N, &M);
	G.resize(N);
	for (int i = 0; i < M; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		--a, --b;
		G[a].push_back(b);
		G[b].push_back(a);
		C[a][b] = c;
		C[b][a] = 0;
		F[a][b] = F[b][a] = 0;
	}
}

int main() {
	freopen(InFile, "r", stdin);
	freopen(OuFile, "w", stdout);
	input();
	printf("%d\n", Dinic());
	return 0;
}