#include<bits/stdc++.h>
using namespace std;

#define mem(x,y)    memset(x,y,sizeof(x))
int n, m;
typedef long long LL;
namespace maxFlow
{
    struct edge {
	int a, b, f, c;
};

const int inf = 1.5e9;
const int MAXN = 5010;

int n, m;
vector <edge> e;
int pt[MAXN]; // very important performance trick
vector <int> g[MAXN];
long long flow = 0;
queue <int> q;
int d[MAXN];
int lim;
int s, t;

void add(int a, int b, int c) {
	edge ed;

	//keep edges in vector: e[ind] - direct edge, e[ind ^ 1] - back edge

	ed.a = a; ed.b = b; ed.f = 0; ed.c = c;
	g[a].push_back(e.size());
	e.push_back(ed);

	ed.a = b; ed.b = a; ed.f = 0; ed.c = c;
	g[b].push_back(e.size());
	e.push_back(ed);
}

bool bfs() {
	for (int i = s; i <= t; i++)
		d[i] = inf;
	d[s] = 0;
	q.push(s);
	while (!q.empty() && d[t] == inf) {
		int cur = q.front(); q.pop();
		for (size_t i = 0; i < g[cur].size(); i++) {
			int id = g[cur][i];
			int to = e[id].b;

			//printf("cur = %d id = %d a = %d b = %d f = %d c = %d\n", cur, id, e[id].a, e[id].b, e[id].f, e[id].c);

			if (d[to] == inf && e[id].c - e[id].f >= lim) {
				d[to] = d[cur] + 1;
				q.push(to);
			}
		}
	}
	while (!q.empty())
		q.pop();
	return d[t] != inf;
}

bool dfs(int v, int flow) {
	if (flow == 0)
		return false;
	if (v == t) {
		//cout << v << endl;
		return true;
	}
	for (; pt[v] < g[v].size(); pt[v]++) {
		int id = g[v][pt[v]];
		int to = e[id].b;

		//printf("v = %d id = %d a = %d b = %d f = %d c = %d\n", v, id, e[id].a, e[id].b, e[id].f, e[id].c);

		if (d[to] == d[v] + 1 && e[id].c - e[id].f >= flow) {
			int pushed = dfs(to, flow);
			if (pushed) {
				e[id].f += flow;
				e[id ^ 1].f -= flow;
				return true;
			}
		}
	}
	return false;
}

LL dinic() {
	for (lim = (1 << 30); lim >= 1;) {
		if (!bfs()) {
			lim >>= 1;
			continue;
		}

		for (int i = s; i <= t; i++)
			pt[i] = 0;

		int pushed;

		while (pushed = dfs(s, lim)) {
			flow = flow + lim;
		}

		//cout << flow << endl;
	}
	return flow;
}
}

int main()
{
//    freopen("in.txt", "r", stdin);
    int i, j, u, v, w;
    scanf("%d %d",&n,&m);
    maxFlow::s = 1, maxFlow::t = n;
    for(int i = 1; i<=m; i++)
    {
        scanf("%d %d %d",&u,&v,&w);
        if(u == v)
            continue;
        maxFlow::add(u,v,w);
    }
    printf("%lld\n",maxFlow::dinic());
}