#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
#define FOR(i, a, b) for(ll i = (a); i < (b); i++)
#define FORD(i, a, b) for(ll i = (b)-1; i >= (a); i--)
typedef vector<int> VI;
typedef vector<VI> VVI;
const ll INF = 1000000000000000000LL;
#define VEI(w,e) ((E[e].u == w) ? E[e].v : E[e].u)
#define CAP(w,e) ((E[e].u == w) ? E[e].cap[0] - E[e].flow : E[e].cap[1] + E[e].flow)
#define ADD(w,e,f) E[e].flow += ((E[e].u == w) ? (f) : (-(f)))
struct Edge { int u, v; ll cap[2], flow; };
VI d, act;
bool bfs(int s, int t, VVI& adj, vector<Edge>& E, ll lim) {
queue<int> Q;
d = VI(adj.size(), -1);
d[t] = 0;
Q.push(t);
while (not Q.empty() and d[s] == -1) {
int u = Q.front(); Q.pop();
for (int i = 0; i < int(adj[u].size()); ++i) {
int e = adj[u][i], v = VEI(u, e);
if (CAP(v, e) >= lim and d[v] == -1) {
d[v] = d[u] + 1;
Q.push(v);
}
}
}
return d[s] >= 0;
}
bool dfs(int u,int t,ll bot,VVI& adj,vector<Edge>& E, ll lim) {
if (bot == 0) return false;
if (u == t) return true;
for (; act[u] < int(adj[u].size()); ++act[u]) {
int e = adj[u][act[u]];
if (CAP(u, e) >= lim and d[u] == d[VEI(u, e)] + 1) {
ll inc=dfs(VEI(u,e),t,min(bot,CAP(u,e)),adj,E,lim);
if (inc) {
ADD(u, e, lim);
return true;
}
}
}
return false;
}
ll maxflow(int s, int t, VVI& adj, vector<Edge>& E) {
for (int i=0; i<int(E.size()); ++i) E[i].flow = 0;
ll flow = 0;
for(int lim = (1<<30); lim >= 1;) {
if(!bfs(s,t,adj,E, lim)) {
lim >>= 1;
continue;
}
act = VI(adj.size(), 0);
while (dfs(s,t,INF, adj, E, lim)) flow += lim;
}
return flow;
}
void addEdge(int u, int v, VVI& adj, vector<Edge>& E, ll cap){
Edge e;
e.u = u;
e.v = v;
e.cap[0] = cap;
e.cap[1] = cap;
e.flow = 0;
adj[u].push_back(E.size());
adj[v].push_back(E.size());
E.push_back(e);
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>>adj(n);
vector<Edge> E;
for(int i = 0; i < m; ++i) {
int x,y,w;
cin >> x >> y >> w;
--x;--y;
addEdge(x, y, adj, E, w);
}
cout << maxflow(0, n-1, adj ,E) << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIGxsID0gbG9uZyBsb25nOwp1c2luZyB2bCA9IHZlY3RvcjxsbD47CiNkZWZpbmUgRk9SKGksIGEsIGIpIGZvcihsbCBpID0gKGEpOyBpIDwgKGIpOyBpKyspCiNkZWZpbmUgRk9SRChpLCBhLCBiKSBmb3IobGwgaSA9IChiKS0xOyBpID49IChhKTsgaS0tKQogCnR5cGVkZWYgdmVjdG9yPGludD4gVkk7CnR5cGVkZWYgdmVjdG9yPFZJPiBWVkk7CmNvbnN0IGxsIElORiA9IDEwMDAwMDAwMDAwMDAwMDAwMDBMTDsKIAojZGVmaW5lIFZFSSh3LGUpICgoRVtlXS51ID09IHcpID8gRVtlXS52IDogRVtlXS51KQojZGVmaW5lIENBUCh3LGUpICgoRVtlXS51ID09IHcpID8gRVtlXS5jYXBbMF0gLSBFW2VdLmZsb3cgOiBFW2VdLmNhcFsxXSArIEVbZV0uZmxvdykKI2RlZmluZSBBREQodyxlLGYpIEVbZV0uZmxvdyArPSAoKEVbZV0udSA9PSB3KSA/IChmKSA6ICgtKGYpKSkKIApzdHJ1Y3QgRWRnZSB7IGludCB1LCB2OyBsbCBjYXBbMl0sIGZsb3c7IH07CiAKVkkgZCwgYWN0OwogCmJvb2wgYmZzKGludCBzLCBpbnQgdCwgVlZJJiBhZGosIHZlY3RvcjxFZGdlPiYgRSwgbGwgbGltKSB7CiAgcXVldWU8aW50PiBROwogIGQgPSBWSShhZGouc2l6ZSgpLCAtMSk7CiAgZFt0XSA9IDA7CiAgUS5wdXNoKHQpOwogIHdoaWxlIChub3QgUS5lbXB0eSgpIGFuZCBkW3NdID09IC0xKSB7CiAgICBpbnQgdSA9IFEuZnJvbnQoKTsgUS5wb3AoKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgaW50KGFkalt1XS5zaXplKCkpOyArK2kpIHsKICAgICAgaW50IGUgPSBhZGpbdV1baV0sIHYgPSBWRUkodSwgZSk7CiAgICAgIGlmIChDQVAodiwgZSkgPj0gbGltIGFuZCBkW3ZdID09IC0xKSB7CiAgICAgICAgZFt2XSA9IGRbdV0gKyAxOwogICAgICAgIFEucHVzaCh2KTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gZFtzXSA+PSAwOwp9CiAKYm9vbCBkZnMoaW50IHUsaW50IHQsbGwgYm90LFZWSSYgYWRqLHZlY3RvcjxFZGdlPiYgRSwgbGwgbGltKSB7CiAgaWYgKGJvdCA9PSAwKSByZXR1cm4gZmFsc2U7CiAgaWYgKHUgPT0gdCkgcmV0dXJuIHRydWU7CiAgZm9yICg7IGFjdFt1XSA8IGludChhZGpbdV0uc2l6ZSgpKTsgKythY3RbdV0pIHsKICAgIGludCBlID0gYWRqW3VdW2FjdFt1XV07CiAgICBpZiAoQ0FQKHUsIGUpID49IGxpbSBhbmQgZFt1XSA9PSBkW1ZFSSh1LCBlKV0gKyAxKSB7CiAgICAgIGxsIGluYz1kZnMoVkVJKHUsZSksdCxtaW4oYm90LENBUCh1LGUpKSxhZGosRSxsaW0pOwogICAgICBpZiAoaW5jKSB7CiAgICAgICAgQUREKHUsIGUsIGxpbSk7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgIH0KICAgIH0KICB9CiAgcmV0dXJuIGZhbHNlOwp9CiAKbGwgbWF4ZmxvdyhpbnQgcywgaW50IHQsIFZWSSYgYWRqLCB2ZWN0b3I8RWRnZT4mIEUpIHsKICBmb3IgKGludCBpPTA7IGk8aW50KEUuc2l6ZSgpKTsgKytpKSBFW2ldLmZsb3cgPSAwOwogIGxsIGZsb3cgPSAwOwogIGZvcihpbnQgbGltID0gKDE8PDMwKTsgbGltID49IDE7KSB7CiAgICBpZighYmZzKHMsdCxhZGosRSwgbGltKSkgewogICAgICBsaW0gPj49IDE7CiAgICAgIGNvbnRpbnVlOwogICAgfQogICAgYWN0ID0gVkkoYWRqLnNpemUoKSwgMCk7CiAgICB3aGlsZSAoZGZzKHMsdCxJTkYsIGFkaiwgRSwgbGltKSkgZmxvdyArPSBsaW07CiAgfQogIHJldHVybiBmbG93Owp9CiAKdm9pZCBhZGRFZGdlKGludCB1LCBpbnQgdiwgVlZJJiBhZGosIHZlY3RvcjxFZGdlPiYgRSwgbGwgY2FwKXsKCUVkZ2UgZTsKCWUudSA9IHU7CgllLnYgPSB2OwoJZS5jYXBbMF0gPSBjYXA7CgllLmNhcFsxXSA9IGNhcDsKCWUuZmxvdyA9IDA7CglhZGpbdV0ucHVzaF9iYWNrKEUuc2l6ZSgpKTsKCWFkalt2XS5wdXNoX2JhY2soRS5zaXplKCkpOwoJRS5wdXNoX2JhY2soZSk7Cn0KaW50IG1haW4oKSB7CglpbnQgbiwgbTsKCWNpbiA+PiBuID4+IG07Cgl2ZWN0b3I8dmVjdG9yPGludD4+YWRqKG4pOwoJdmVjdG9yPEVkZ2U+IEU7Cglmb3IoaW50IGkgPSAwOyBpIDwgbTsgKytpKSB7CgkJaW50IHgseSx3OwoJCWNpbiA+PiB4ID4+IHkgPj4gdzsKCQktLXg7LS15OwoJCWFkZEVkZ2UoeCwgeSwgYWRqLCBFLCB3KTsKCX0KCWNvdXQgPDwgbWF4ZmxvdygwLCBuLTEsIGFkaiAsRSkgPDwgZW5kbDsKfQ==