P1019

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 10010, M = 100010;
const ll INF = 1e14;
int n, m, s, t;
int head[N], to[M << 1], cap[M << 1], nxt[M << 1], idx = 0;
int dep[N], cur[N];

void add(int u, int v, int c)
{
    to[idx] = v;
    cap[idx] = c;
    nxt[idx] = head[u];
    head[u] = idx ++;
    return;
}
bool bfsearch(void)
{
    queue<int> q;
    memset(dep, -1, sizeof(dep));
    dep[s] = 0, cur[s] = head[s], q.push(s);

    while (!q.empty())
    {
        int fro = q.front(); q.pop();
        for (int i = head[fro]; i != -1; i = nxt[i])
        {
            int e = to[i];
            if (dep[e] == -1 && cap[i])
            {
                cur[e] = head[e];
                dep[e] = dep[fro] + 1;
                if (e == t)
                    return true;
                q.push(e);
            }
        }
    }
    return false;
}
ll extraRoad(int u, ll lim)
{
    if (u == t) return lim;
    ll flow = 0;
    for (int i = cur[u]; i != -1 && flow < lim; i = nxt[i])
    {
        cur[u] = i; int e = to[i];
        if (dep[e] == dep[u] + 1 && cap[i])
        {
            int del = extraRoad(e, min(1ll * cap[i], lim - flow));
            if (!del)
                dep[e] = -1;
            flow += del, cap[i] -= del, cap[i xor 1] += del;
        }
    }
    return flow;
}
ll Dinic(void)
{
    ll res = 0, flow;
    while (bfsearch())
        while (flow = extraRoad(s, INF))
            res += flow;
    return res;
}

int main()
{
    memset(head, -1, sizeof(head));

    scanf("%d%d%d%d", &n, &m, &s, &t);
    int inpu, inpv, inpc;
    for (int i = 1; i <= m; i ++)
    {
        scanf("%d%d%d", &inpu, &inpv, &inpc);
        add(inpu, inpv, inpc), add(inpv, inpu, 0);
    }
    printf("%lld\n", Dinic());
    return 0;
}