#include <bits/stdc++.h>
#define MODL 1000000000000000003
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=5000+9;
int n,m;
int par[N],lev[N];
vector<int> adj[N];
map<pii,ll> edg;
ll dfs(int v,int p,ll mn){
ll tosub=0;
for(auto u:adj[v])if(u!=p && lev[u]==lev[v]+1 && edg[mp(v,u)]>0){
ll nmn=min(1ll*mn,edg[mp(v,u)]);
if(u==n){
edg[mp(v,u)]-=nmn;
edg[mp(u,v)]+=nmn;
return nmn;
}
ll sub=dfs(u,v,nmn);
tosub+=sub;
if(sub){
edg[mp(v,u)]-=sub;
edg[mp(u,v)]+=sub;
}
}
return tosub;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int tt=1;//cin>>tt;
while(tt--){
edg.clear();
cin>>n>>m;
for(int i=0;i<=n;i++){
adj[i].clear();
}
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
if(x==y)continue;
adj[x].pb(y);
adj[y].pb(x);
edg[mp(x,y)]+=z;
edg[mp(y,x)]+=z;
}
ll ans=0;
while(1){
// bfs to find augmenting path
queue<int> q;
for(int i=0;i<=n;i++){
par[i]=lev[i]=-1;
}
par[1]=0;lev[1]=1;
q.push(1);
bool done=0;
while(!q.empty()){
int v=q.front(); q.pop();
for(auto u:adj[v])if((lev[u]==-1 || lev[u]>lev[v]) && par[u]==-1 && edg[mp(v,u)]>0){
if(lev[u]==-1)lev[u]=lev[v]+1;
par[u]=v;
if(u==n){
done=1;
break;
}
q.push(u);
}
if(done)break;
}
if(done){
// find blocking flow
ll add=dfs(1,0,MODL);
ans+=add;
} else break;
}
cout<<ans<<endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgTU9ETCAxMDAwMDAwMDAwMDAwMDAwMDAzCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KI2RlZmluZSBtcCBtYWtlX3BhaXIKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOPTUwMDArOTsKaW50IG4sbTsKaW50IHBhcltOXSxsZXZbTl07CnZlY3RvcjxpbnQ+IGFkaltOXTsKbWFwPHBpaSxsbD4gZWRnOwpsbCBkZnMoaW50IHYsaW50IHAsbGwgbW4pewogICAgCiAgICBsbCB0b3N1Yj0wOwogICAgZm9yKGF1dG8gdTphZGpbdl0paWYodSE9cCAmJiBsZXZbdV09PWxldlt2XSsxICYmIGVkZ1ttcCh2LHUpXT4wKXsKICAgICAgICBsbCBubW49bWluKDFsbCptbixlZGdbbXAodix1KV0pOwogICAgICAgIGlmKHU9PW4pewogICAgICAgICAgICBlZGdbbXAodix1KV0tPW5tbjsKICAgICAgICAgICAgZWRnW21wKHUsdildKz1ubW47CiAgICAgICAgICAgIHJldHVybiBubW47CiAgICAgICAgfQogICAgICAgIGxsIHN1Yj1kZnModSx2LG5tbik7CiAgICAgICAgdG9zdWIrPXN1YjsKICAgICAgICBpZihzdWIpewogICAgICAgICAgICBlZGdbbXAodix1KV0tPXN1YjsKICAgICAgICAgICAgZWRnW21wKHUsdildKz1zdWI7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHRvc3ViOwoKfQppbnQgbWFpbigpCnsgCgogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoMCk7CiAgICBpbnQgdHQ9MTsvL2Npbj4+dHQ7CiAgICB3aGlsZSh0dC0tKXsKICAgICAgICBlZGcuY2xlYXIoKTsKICAgICAgICBjaW4+Pm4+Pm07CiAgICAgICAgZm9yKGludCBpPTA7aTw9bjtpKyspewogICAgICAgICAgICBhZGpbaV0uY2xlYXIoKTsKICAgICAgICB9CiAgICAgICAgZm9yKGludCBpPTA7aTxtO2krKyl7CiAgICAgICAgICAgIGludCB4LHksejsKICAgICAgICAgICAgY2luPj54Pj55Pj56OwogICAgICAgICAgICBpZih4PT15KWNvbnRpbnVlOwogICAgICAgICAgICBhZGpbeF0ucGIoeSk7CiAgICAgICAgICAgIGFkalt5XS5wYih4KTsKICAgICAgICAgICAgZWRnW21wKHgseSldKz16OwogICAgICAgICAgICBlZGdbbXAoeSx4KV0rPXo7CgogICAgICAgIH0KICAgICAgICBsbCBhbnM9MDsKICAgICAgICB3aGlsZSgxKXsKCiAgICAgICAgICAgIC8vIGJmcyB0byBmaW5kIGF1Z21lbnRpbmcgcGF0aAogICAgICAgICAgICBxdWV1ZTxpbnQ+IHE7CiAgICAgICAgICAgIGZvcihpbnQgaT0wO2k8PW47aSsrKXsKICAgICAgICAgICAgICAgIHBhcltpXT1sZXZbaV09LTE7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcGFyWzFdPTA7bGV2WzFdPTE7CiAgICAgICAgICAgIHEucHVzaCgxKTsKICAgICAgICAgICAgYm9vbCBkb25lPTA7CiAgICAgICAgICAgIHdoaWxlKCFxLmVtcHR5KCkpewogICAgICAgICAgICAgICAgaW50IHY9cS5mcm9udCgpOyBxLnBvcCgpOwogICAgICAgICAgICAgICAgZm9yKGF1dG8gdTphZGpbdl0paWYoKGxldlt1XT09LTEgfHwgbGV2W3VdPmxldlt2XSkgJiYgcGFyW3VdPT0tMSAmJiBlZGdbbXAodix1KV0+MCl7CiAgICAgICAgICAgICAgICAgICAgaWYobGV2W3VdPT0tMSlsZXZbdV09bGV2W3ZdKzE7CiAgICAgICAgICAgICAgICAgICAgcGFyW3VdPXY7CiAgICAgICAgICAgICAgICAgICAgaWYodT09bil7CiAgICAgICAgICAgICAgICAgICAgICAgIGRvbmU9MTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIHEucHVzaCh1KTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmKGRvbmUpYnJlYWs7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYoZG9uZSl7CiAgICAgICAgICAgICAgICAvLyBmaW5kIGJsb2NraW5nIGZsb3cKICAgICAgICAgICAgICAgIGxsIGFkZD1kZnMoMSwwLE1PREwpOwogICAgICAgICAgICAgICAgYW5zKz1hZGQ7CiAgICAgICAgICAgIH0gZWxzZSBicmVhazsKCiAgICAgICAgfQogICAgICAgIGNvdXQ8PGFuczw8ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9IA==