#include<bits/stdc++.h>
#define ll long long int
#define pp pair<int,int> >
#define mp make_pair
#define chk(a) cout<<#a<<" : "<<a<<"\n";
#define chk2(a,b) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<"\n";
#define chk3(a,b,c) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<"\n";
#define chk4(a,b,c,d) cout<<#a<<" : "<<a<<", "<<#b<<" : "<<b<<", "<<#c<<" : "<<c<<", "<<#d<<" : "<<d<<"\n";
#define M 1000000007
#define F first
#define S second
#define prev prevword
using namespace std;
int n;
ll powe(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)
ans=(ans*a)%M;
b=b/2;
a=(a*a)%M;
}
return ans;
}
ll mini(ll a,ll b)
{
if(a<b)
return a;
return b;
}
ll gcde(ll a,ll b)
{
if(b==0)
return a;
return gcde(b,a%b);
}
ll cap[5009][5009];
ll flow[5009][5009];
int d[5009],prev[5009];
vector<int> gph[5009];
int q[5009];
bool bfs()
{
int u=1;
memset(d,-1,sizeof(d));
d[1]=0;
prev[u]=-1;
int sx,ex;
sx=0;ex=-1;
q[++ex]=1;
while(sx<=ex and sx!=-1)
{
u=q[sx++];
for(int i=0;i<gph[u].size();i++)
{
int to=gph[u][i];
if(d[to]==-1 and cap[u][to]-flow[u][to]>0)
{
d[to]=d[u]+1;
q[++ex]=to;
}
}
}
return (d[n]!=-1);
}
ll dfs(int u,ll fl)
{
if(u==n)
return fl;
for(int i=0;i<gph[u].size();i++)
{
int to=gph[u][i];
if(cap[u][to]-flow[u][to]>0 and d[to]==d[u]+1)
{
fl=mini(fl,cap[u][to]-flow[u][to]);
int df=dfs(to,fl);
if(df>0)
{
flow[u][to]+=df;
flow[to][u]-=df;
return df;
}
}
}
d[u] = 1000000042ll;
return 0;
}
int main()
{
int m,i,u,v,c;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&c);
if(cap[u][v])
{
cap[u][v]+=c;
cap[v][u]+=c;
}
else if(u!=v)
{
gph[u].push_back(v);
gph[v].push_back(u);
cap[u][v]+=c;
cap[v][u]+=c;
}
}
ll ans=0;
while(bfs())
{
while(true)
{
int df=dfs(1,1e15);
if(df==0)
break;
ans+=df;
}
}
printf("%lld\n",ans);
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CiNkZWZpbmUgcHAgcGFpcjxpbnQsaW50PiA+CiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgY2hrKGEpCWNvdXQ8PCNhPDwiIDogIjw8YTw8IlxuIjsKI2RlZmluZSBjaGsyKGEsYikgY291dDw8I2E8PCIgOiAiPDxhPDwiLCAiPDwjYjw8IiA6ICI8PGI8PCJcbiI7CiNkZWZpbmUgY2hrMyhhLGIsYykgY291dDw8I2E8PCIgOiAiPDxhPDwiLCAiPDwjYjw8IiA6ICI8PGI8PCIsICI8PCNjPDwiIDogIjw8Yzw8IlxuIjsKI2RlZmluZSBjaGs0KGEsYixjLGQpIGNvdXQ8PCNhPDwiIDogIjw8YTw8IiwgIjw8I2I8PCIgOiAiPDxiPDwiLCAiPDwjYzw8IiA6ICI8PGM8PCIsICI8PCNkPDwiIDogIjw8ZDw8IlxuIjsKI2RlZmluZSBNIDEwMDAwMDAwMDcKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBwcmV2IHByZXZ3b3JkCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBuOwpsbCBwb3dlKGxsIGEsbGwgYikKewoJbGwgYW5zPTE7Cgl3aGlsZShiKQoJewoJCWlmKGImMSkKCQkJYW5zPShhbnMqYSklTTsKCQliPWIvMjsKCQlhPShhKmEpJU07Cgl9CglyZXR1cm4gYW5zOwp9CmxsIG1pbmkobGwgYSxsbCBiKQp7CiAgICBpZihhPGIpCiAgICAgICAgcmV0dXJuIGE7CiAgICAgICAgcmV0dXJuIGI7Cn0KbGwgZ2NkZShsbCBhLGxsIGIpCnsKCWlmKGI9PTApCgkJcmV0dXJuIGE7CglyZXR1cm4gZ2NkZShiLGElYik7Cn0KCmxsIGNhcFs1MDA5XVs1MDA5XTsKbGwgZmxvd1s1MDA5XVs1MDA5XTsKaW50IGRbNTAwOV0scHJldls1MDA5XTsKdmVjdG9yPGludD4gZ3BoWzUwMDldOwppbnQgcVs1MDA5XTsKYm9vbCBiZnMoKQp7CiAgICBpbnQgdT0xOwogICAgbWVtc2V0KGQsLTEsc2l6ZW9mKGQpKTsKCiAgICBkWzFdPTA7CiAgICBwcmV2W3VdPS0xOwogICAgaW50IHN4LGV4OwogICAgc3g9MDtleD0tMTsKICAgIHFbKytleF09MTsKICAgIHdoaWxlKHN4PD1leCBhbmQgc3ghPS0xKQogICAgewogICAgICAgIHU9cVtzeCsrXTsKICAgICAgICBmb3IoaW50IGk9MDtpPGdwaFt1XS5zaXplKCk7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHRvPWdwaFt1XVtpXTsKICAgICAgICAgICAgaWYoZFt0b109PS0xIGFuZCBjYXBbdV1bdG9dLWZsb3dbdV1bdG9dPjApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGRbdG9dPWRbdV0rMTsKICAgICAgICAgICAgICAgIHFbKytleF09dG87CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gKGRbbl0hPS0xKTsKfQoKbGwgZGZzKGludCB1LGxsIGZsKQp7CiAgICBpZih1PT1uKQogICAgICAgIHJldHVybiBmbDsKICAgIGZvcihpbnQgaT0wO2k8Z3BoW3VdLnNpemUoKTtpKyspCiAgICB7CiAgICAgICAgaW50IHRvPWdwaFt1XVtpXTsKICAgICAgICBpZihjYXBbdV1bdG9dLWZsb3dbdV1bdG9dPjAgYW5kIGRbdG9dPT1kW3VdKzEpCiAgICAgICAgewogICAgICAgICAgICBmbD1taW5pKGZsLGNhcFt1XVt0b10tZmxvd1t1XVt0b10pOwogICAgICAgICAgICBpbnQgZGY9ZGZzKHRvLGZsKTsKICAgICAgICAgICAgaWYoZGY+MCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBmbG93W3VdW3RvXSs9ZGY7CiAgICAgICAgICAgICAgICBmbG93W3RvXVt1XS09ZGY7CiAgICAgICAgICAgICAgICByZXR1cm4gZGY7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBkW3VdID0gMTAwMDAwMDA0MmxsOwogICAgcmV0dXJuIDA7Cn0KaW50IG1haW4oKQp7CiAgICBpbnQgbSxpLHUsdixjOwogICAgc2NhbmYoIiVkJWQiLCZuLCZtKTsKCiAgICBmb3IoaT0wO2k8bTtpKyspCiAgICB7CiAgICAgICAgc2NhbmYoIiVkJWQlZCIsJnUsJnYsJmMpOwogICAgICAgIGlmKGNhcFt1XVt2XSkKICAgICAgICB7CiAgICAgICAgICAgIGNhcFt1XVt2XSs9YzsKICAgICAgICAgICAgY2FwW3ZdW3VdKz1jOwogICAgICAgIH0KICAgICAgICBlbHNlIGlmKHUhPXYpCiAgICAgICAgewogICAgICAgICAgICBncGhbdV0ucHVzaF9iYWNrKHYpOwogICAgICAgICAgICBncGhbdl0ucHVzaF9iYWNrKHUpOwogICAgICAgICAgICBjYXBbdV1bdl0rPWM7CiAgICAgICAgICAgIGNhcFt2XVt1XSs9YzsKICAgICAgICB9CiAgICB9CiAgICBsbCBhbnM9MDsKICAgICAgICB3aGlsZShiZnMoKSkKICAgICAgICB7CiAgICAgICAgICAgIHdoaWxlKHRydWUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBkZj1kZnMoMSwxZTE1KTsKCiAgICAgICAgICAgICAgICBpZihkZj09MCkKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIGFucys9ZGY7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcHJpbnRmKCIlbGxkXG4iLGFucyk7CiAgICAgICAgcmV0dXJuIDA7Cn0K