Sktic @ 2021-01-31 18:17:03
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const ll INF=0xffffffff;
ll n,m,s,t;
struct node
{
ll v;
ll val;
ll nextv;
};
struct node2
{
int before;
int b;
};
node c[maxn];
ll vis[maxn]={};
ll hd[maxn];
ll k=1;
node2 p[maxn]={};
void add(ll ur,ll vr,ll valr)
{
k++;
c[k].v=vr;
c[k].val=valr;
c[k].nextv=hd[ur];
hd[ur]=k;
}
bool bfs()
{
memset(p,-1,sizeof(p));
memset(vis,0,sizeof(vis));
queue<int>q;
vis[s]=1;
q.push(s);
while(!q.empty())
{
ll r=q.front();
for(ll i=hd[r];i!=0;i=c[i].nextv)
{
ll h=c[i].v;
if(vis[h]==0&&c[i].val!=0)
{
p[h].before=r;
p[h].b=i;
if(h==t)
return true;
vis[h]=1;
q.push(h);
}
}
q.pop();
}
return false;
}
ll EK()
{
ll ans=0;
while(bfs())
{
ll mn=INF;
for(int i=t;i!=s;i=p[i].before)
{
mn=min(mn,c[p[i].b].val);
}
for(int i=t;i!=s;i=p[i].before)
{
c[p[i].b].val=c[p[i].b].val-mn;
c[p[i].b^1].val=c[p[i].b^1].val+mn;
}
ans+=mn;
}
return ans;
}
int main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
ll u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,w,0);
}
cout<<EK();
return 0;
}