#include<bits/stdc++.h>
using namespace std;
vector<int> dist;
vector<int> ptr;
vector< vector<int> > graph(5000);
long long cap[5009][5009];
long long flow[5009][5009];
int n;
bool bfs(int source, int sink)
{
queue<int> q;
vector<int> visited(n,false);
int i,j,v;
dist.resize(n);
ptr.resize(n);
for(i=0;i<n;i++)
dist[i]= ptr[i]= 0;
q.push(source);
visited[source]=true;
while(!q.empty())
{
v = q.front();
q.pop();
for (i=0;i<graph[v].size();i++)
{
j = graph[v][i];
if (!visited[j] && cap[v][j] - flow[v][j]>0)
{
q.push(j);
dist[j] = dist[v]+1;
visited[j] = true;
}
}
}
if(visited[sink])
return true;
return false;
}
long long dinic(int v, int sink, long long flo)
{
if (v == sink || flo == 0)
return flo;
long long fl = 0;
int j;
for(;ptr[v]<graph[v].size();++ptr[v])
{
j = graph[v][ptr[v]];
if(cap[v][j] - flow[v][j] >0 && dist[j] == dist[v]+1)
{
long long f = dinic(j, sink, min(flo,cap[v][j] - flow[v][j]));
if(f == 0)
continue;
flow[v][j] += f;
flow[j][v] -= f;
return f;
}
}
dist[v] = INT_MAX;
return 0;
}
long long max_flow(int source, int sink)
{
long long flo = 0, f;
while(bfs(source, sink))
{
f = dinic(source,sink,LONG_LONG_MAX);
flo += f;
if(f == 0)
break;
}
return flo;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int m;
cin>>n>>m;
int u,v,w;
for(int i=0;i<m;i++)
{
cin>>u>>v>>w;
u--;
v--;
if (cap[u][v])
{
cap[u][v] += w;
cap[v][u] += w;
}
else
{
cap[u][v] += w;
cap[v][u] += w;
graph[v].push_back(u);
graph[u].push_back(v);
}
}
cout<<max_flow(0, n-1)<<endl;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAp2ZWN0b3I8aW50PiBkaXN0Owp2ZWN0b3I8aW50PiBwdHI7CnZlY3RvcjwgdmVjdG9yPGludD4gPiBncmFwaCg1MDAwKTsKbG9uZyBsb25nIGNhcFs1MDA5XVs1MDA5XTsKbG9uZyBsb25nIGZsb3dbNTAwOV1bNTAwOV07CgppbnQgbjsKIApib29sIGJmcyhpbnQgc291cmNlLCBpbnQgc2luaykKewoJcXVldWU8aW50PiBxOwoJdmVjdG9yPGludD4gdmlzaXRlZChuLGZhbHNlKTsKCQoJaW50IGksaix2OwoJZGlzdC5yZXNpemUobik7CglwdHIucmVzaXplKG4pOwoKCWZvcihpPTA7aTxuO2krKykKCQlkaXN0W2ldPSBwdHJbaV09IDA7CgkJCglxLnB1c2goc291cmNlKTsKCXZpc2l0ZWRbc291cmNlXT10cnVlOwoJd2hpbGUoIXEuZW1wdHkoKSkKCXsKCQl2ID0gcS5mcm9udCgpOwoJCXEucG9wKCk7CgkJZm9yIChpPTA7aTxncmFwaFt2XS5zaXplKCk7aSsrKQoJCXsKCQkJaiA9IGdyYXBoW3ZdW2ldOwoJCQlpZiAoIXZpc2l0ZWRbal0gJiYgY2FwW3ZdW2pdIC0gZmxvd1t2XVtqXT4wKQoJCQl7CgkJCQlxLnB1c2goaik7CgkJCQlkaXN0W2pdID0gZGlzdFt2XSsxOwoJCQkJdmlzaXRlZFtqXSA9IHRydWU7CgkJCX0KCQl9Cgl9CiAKCWlmKHZpc2l0ZWRbc2lua10pCgkJcmV0dXJuIHRydWU7CglyZXR1cm4gZmFsc2U7Cn0KIApsb25nIGxvbmcgZGluaWMoaW50IHYsIGludCBzaW5rLCBsb25nIGxvbmcgZmxvKQp7CglpZiAodiA9PSBzaW5rIHx8IGZsbyA9PSAwKQoJCXJldHVybiBmbG87CiAKCWxvbmcgbG9uZyBmbCA9IDA7CglpbnQgajsKCWZvcig7cHRyW3ZdPGdyYXBoW3ZdLnNpemUoKTsrK3B0clt2XSkKCXsKCQlqID0gZ3JhcGhbdl1bcHRyW3ZdXTsKCQlpZihjYXBbdl1bal0gLSBmbG93W3ZdW2pdID4wICYmIGRpc3Rbal0gPT0gZGlzdFt2XSsxKQoJCXsKCQkJCgkJCWxvbmcgbG9uZyBmID0gZGluaWMoaiwgc2luaywgbWluKGZsbyxjYXBbdl1bal0gLSBmbG93W3ZdW2pdKSk7CgkJCWlmKGYgPT0gMCkKCQkJCWNvbnRpbnVlOwoJCQlmbG93W3ZdW2pdICs9IGY7CgkJCWZsb3dbal1bdl0gLT0gZjsKCQkJcmV0dXJuIGY7CgkJfQogCgl9CglkaXN0W3ZdID0gSU5UX01BWDsKCXJldHVybiAwOwp9CiAKbG9uZyBsb25nIG1heF9mbG93KGludCBzb3VyY2UsIGludCBzaW5rKQp7Cglsb25nIGxvbmcgZmxvID0gMCwgZjsKCXdoaWxlKGJmcyhzb3VyY2UsIHNpbmspKQoJewoJCWYgPSBkaW5pYyhzb3VyY2Usc2luayxMT05HX0xPTkdfTUFYKTsKCQlmbG8gKz0gZjsKCQlpZihmID09IDApCgkJCWJyZWFrOwoJfQoJcmV0dXJuIGZsbzsKCQp9CiAKaW50IG1haW4oKQp7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoMCk7CgkJCglpbnQgbTsKCWNpbj4+bj4+bTsKCWludCB1LHYsdzsKCQkJCglmb3IoaW50IGk9MDtpPG07aSsrKQoJewoJCWNpbj4+dT4+dj4+dzsKCQl1LS07CgkJdi0tOwoJCWlmIChjYXBbdV1bdl0pCgkJewoJCQljYXBbdV1bdl0gKz0gdzsKCQkJY2FwW3ZdW3VdICs9IHc7CgkJfQoJCWVsc2UKCQl7CgkJCWNhcFt1XVt2XSArPSB3OwoJCQljYXBbdl1bdV0gKz0gdzsKCQkJZ3JhcGhbdl0ucHVzaF9iYWNrKHUpOwoJCQlncmFwaFt1XS5wdXNoX2JhY2sodik7CgkJfQoJfQoJY291dDw8bWF4X2Zsb3coMCwgbi0xKTw8ZW5kbDsKfSAK