#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1205;
template <int MAXN, class T = int> struct HLPP {
const T INF = numeric_limits<T>::max();
struct edge {
int to, rev;
T f;
};
int s = MAXN - 1, t = MAXN - 2;
vector<edge> edges[MAXN];
vector<int> lst[MAXN], gap[MAXN];
T excess[MAXN];
int highest, height[MAXN], cnt[MAXN];
void addEdge(int from, int to, int f, bool isDirected = true) {
edges[from].push_back({to, (int)edges[to].size(), f});
edges[to].push_back({from, (int)edges[from].size() - 1, isDirected ? 0 : f});
}
void updHeight(int v, int nh) {
if (height[v] != MAXN)
cnt[height[v]]--;
height[v] = nh;
if (nh == MAXN)
return;
cnt[nh]++, highest = nh;
gap[nh].push_back(v);
if (excess[v] > 0) {
gap[nh].push_back(v);
lst[nh].push_back(v);
}
}
void globalRelabel() {
fill(begin(height), end(height), MAXN);
fill(begin(cnt), end(cnt), 0);
for (int i = 0; i < MAXN; i++) {
lst[i].clear();
gap[i].clear();
}
height[t] = 0;
queue<int> q({t});
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto &e : edges[v]) {
if (height[e.to] != MAXN || edges[e.to][e.rev].f <= 0)
continue;
updHeight(e.to, height[v] + 1);
q.push(e.to);
}
highest = height[v];
}
}
void push(int v, edge &e) {
if (excess[e.to] == 0)
lst[height[e.to]].push_back(e.to);
T df = min(excess[v], e.f);
e.f -= df, edges[e.to][e.rev].f += df;
excess[v] -= df, excess[e.to] += df;
}
int work = 0;
void discharge(int v) {
int nh = MAXN;
for (auto &e : edges[v]) {
if (e.f <= 0)
continue;
if (height[v] == height[e.to] + 1) {
push(v, e);
if (excess[v] <= 0)
return;
} else
nh = min(nh, height[e.to] + 1);
}
work++;
if (cnt[height[v]] > 1)
updHeight(v, nh);
else {
for (int i = height[v]; i <= highest; i++) {
for (auto j : gap[i])
updHeight(j, MAXN);
gap[i].clear();
}
}
}
T calc(int n) {
fill(begin(excess), end(excess), 0);
excess[s] = INF, excess[t] = -INF;
globalRelabel();
for (auto &e : edges[s])
push(s, e);
for (; highest >= 0; highest--) {
while (!lst[highest].empty()) {
int v = lst[highest].back();
lst[highest].pop_back();
discharge(v);
if (work > 4 * n) {
globalRelabel();
work = 0;
}
}
}
return excess[t] + INF;
}
};
HLPP<MAXN, long long> hlpp;
inline void scan_int(int *p) {
static char c;
while ((c = getchar_unlocked()) < '0')
; // just to be safe
for (*p = c - '0'; (c = getchar_unlocked()) >= '0'; *p = *p * 10 + c - '0')
;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
scan_int(&n), scan_int(&m);
// cin >> n >> m;
int s = 1, t = n;
scan_int(&s), scan_int(&t);
// cin >> s >> t;
for (int i = 0, u, v, f; i < m; ++i) {
scan_int(&u), scan_int(&v), scan_int(&f);
// cin >> u >> v >> f;
hlpp.addEdge(u, v, f, true);
}
hlpp.s = s, hlpp.t = t;
cout << hlpp.calc(n) << endl;
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoMykKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE1BWE4gPSAxMjA1Owp0ZW1wbGF0ZSA8aW50IE1BWE4sIGNsYXNzIFQgPSBpbnQ+IHN0cnVjdCBITFBQIHsKICAgIGNvbnN0IFQgSU5GID0gbnVtZXJpY19saW1pdHM8VD46Om1heCgpOwogICAgc3RydWN0IGVkZ2UgewogICAgICAgIGludCB0bywgcmV2OwogICAgICAgIFQgZjsKICAgIH07CiAgICBpbnQgcyA9IE1BWE4gLSAxLCB0ID0gTUFYTiAtIDI7CiAgICB2ZWN0b3I8ZWRnZT4gZWRnZXNbTUFYTl07CiAgICB2ZWN0b3I8aW50PiBsc3RbTUFYTl0sIGdhcFtNQVhOXTsKICAgIFQgZXhjZXNzW01BWE5dOwogICAgaW50IGhpZ2hlc3QsIGhlaWdodFtNQVhOXSwgY250W01BWE5dOwogICAgdm9pZCBhZGRFZGdlKGludCBmcm9tLCBpbnQgdG8sIGludCBmLCBib29sIGlzRGlyZWN0ZWQgPSB0cnVlKSB7CiAgICAgICAgZWRnZXNbZnJvbV0ucHVzaF9iYWNrKHt0bywgKGludCllZGdlc1t0b10uc2l6ZSgpLCBmfSk7CiAgICAgICAgZWRnZXNbdG9dLnB1c2hfYmFjayh7ZnJvbSwgKGludCllZGdlc1tmcm9tXS5zaXplKCkgLSAxLCBpc0RpcmVjdGVkID8gMCA6IGZ9KTsKICAgIH0KICAgIHZvaWQgdXBkSGVpZ2h0KGludCB2LCBpbnQgbmgpIHsKICAgICAgICBpZiAoaGVpZ2h0W3ZdICE9IE1BWE4pCiAgICAgICAgICAgIGNudFtoZWlnaHRbdl1dLS07CiAgICAgICAgaGVpZ2h0W3ZdID0gbmg7CiAgICAgICAgaWYgKG5oID09IE1BWE4pCiAgICAgICAgICAgIHJldHVybjsKICAgICAgICBjbnRbbmhdKyssIGhpZ2hlc3QgPSBuaDsKICAgICAgICBnYXBbbmhdLnB1c2hfYmFjayh2KTsKICAgICAgICBpZiAoZXhjZXNzW3ZdID4gMCkgewogICAgICAgICAgICBnYXBbbmhdLnB1c2hfYmFjayh2KTsKICAgICAgICAgICAgbHN0W25oXS5wdXNoX2JhY2sodik7CiAgICAgICAgfQogICAgfQogICAgdm9pZCBnbG9iYWxSZWxhYmVsKCkgewogICAgICAgIGZpbGwoYmVnaW4oaGVpZ2h0KSwgZW5kKGhlaWdodCksIE1BWE4pOwogICAgICAgIGZpbGwoYmVnaW4oY250KSwgZW5kKGNudCksIDApOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTUFYTjsgaSsrKSB7CiAgICAgICAgICAgIGxzdFtpXS5jbGVhcigpOwogICAgICAgICAgICBnYXBbaV0uY2xlYXIoKTsKICAgICAgICB9CiAgICAgICAgaGVpZ2h0W3RdID0gMDsKICAgICAgICBxdWV1ZTxpbnQ+IHEoe3R9KTsKICAgICAgICB3aGlsZSAoIXEuZW1wdHkoKSkgewogICAgICAgICAgICBpbnQgdiA9IHEuZnJvbnQoKTsKICAgICAgICAgICAgcS5wb3AoKTsKICAgICAgICAgICAgZm9yIChhdXRvICZlIDogZWRnZXNbdl0pIHsKICAgICAgICAgICAgICAgIGlmIChoZWlnaHRbZS50b10gIT0gTUFYTiB8fCBlZGdlc1tlLnRvXVtlLnJldl0uZiA8PSAwKQogICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgdXBkSGVpZ2h0KGUudG8sIGhlaWdodFt2XSArIDEpOwogICAgICAgICAgICAgICAgcS5wdXNoKGUudG8pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGhpZ2hlc3QgPSBoZWlnaHRbdl07CiAgICAgICAgfQogICAgfQogICAgdm9pZCBwdXNoKGludCB2LCBlZGdlICZlKSB7CiAgICAgICAgaWYgKGV4Y2Vzc1tlLnRvXSA9PSAwKQogICAgICAgICAgICBsc3RbaGVpZ2h0W2UudG9dXS5wdXNoX2JhY2soZS50byk7CiAgICAgICAgVCBkZiA9IG1pbihleGNlc3Nbdl0sIGUuZik7CiAgICAgICAgZS5mIC09IGRmLCBlZGdlc1tlLnRvXVtlLnJldl0uZiArPSBkZjsKICAgICAgICBleGNlc3Nbdl0gLT0gZGYsIGV4Y2Vzc1tlLnRvXSArPSBkZjsKICAgIH0KICAgIGludCB3b3JrID0gMDsKICAgIHZvaWQgZGlzY2hhcmdlKGludCB2KSB7CiAgICAgICAgaW50IG5oID0gTUFYTjsKICAgICAgICBmb3IgKGF1dG8gJmUgOiBlZGdlc1t2XSkgewogICAgICAgICAgICBpZiAoZS5mIDw9IDApCiAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgaWYgKGhlaWdodFt2XSA9PSBoZWlnaHRbZS50b10gKyAxKSB7CiAgICAgICAgICAgICAgICBwdXNoKHYsIGUpOwogICAgICAgICAgICAgICAgaWYgKGV4Y2Vzc1t2XSA8PSAwKQogICAgICAgICAgICAgICAgICAgIHJldHVybjsKICAgICAgICAgICAgfSBlbHNlCiAgICAgICAgICAgICAgICBuaCA9IG1pbihuaCwgaGVpZ2h0W2UudG9dICsgMSk7CiAgICAgICAgfQogICAgICAgIHdvcmsrKzsKICAgICAgICBpZiAoY250W2hlaWdodFt2XV0gPiAxKQogICAgICAgICAgICB1cGRIZWlnaHQodiwgbmgpOwogICAgICAgIGVsc2UgewogICAgICAgICAgICBmb3IgKGludCBpID0gaGVpZ2h0W3ZdOyBpIDw9IGhpZ2hlc3Q7IGkrKykgewogICAgICAgICAgICAgICAgZm9yIChhdXRvIGogOiBnYXBbaV0pCiAgICAgICAgICAgICAgICAgICAgdXBkSGVpZ2h0KGosIE1BWE4pOwogICAgICAgICAgICAgICAgZ2FwW2ldLmNsZWFyKCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBUIGNhbGMoaW50IG4pIHsKICAgICAgICBmaWxsKGJlZ2luKGV4Y2VzcyksIGVuZChleGNlc3MpLCAwKTsKICAgICAgICBleGNlc3Nbc10gPSBJTkYsIGV4Y2Vzc1t0XSA9IC1JTkY7CiAgICAgICAgZ2xvYmFsUmVsYWJlbCgpOwogICAgICAgIGZvciAoYXV0byAmZSA6IGVkZ2VzW3NdKQogICAgICAgICAgICBwdXNoKHMsIGUpOwogICAgICAgIGZvciAoOyBoaWdoZXN0ID49IDA7IGhpZ2hlc3QtLSkgewogICAgICAgICAgICB3aGlsZSAoIWxzdFtoaWdoZXN0XS5lbXB0eSgpKSB7CiAgICAgICAgICAgICAgICBpbnQgdiA9IGxzdFtoaWdoZXN0XS5iYWNrKCk7CiAgICAgICAgICAgICAgICBsc3RbaGlnaGVzdF0ucG9wX2JhY2soKTsKICAgICAgICAgICAgICAgIGRpc2NoYXJnZSh2KTsKICAgICAgICAgICAgICAgIGlmICh3b3JrID4gNCAqIG4pIHsKICAgICAgICAgICAgICAgICAgICBnbG9iYWxSZWxhYmVsKCk7CiAgICAgICAgICAgICAgICAgICAgd29yayA9IDA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGV4Y2Vzc1t0XSArIElORjsKICAgIH0KfTsKCkhMUFA8TUFYTiwgbG9uZyBsb25nPiBobHBwOwoKaW5saW5lIHZvaWQgc2Nhbl9pbnQoaW50ICpwKSB7CiAgICBzdGF0aWMgY2hhciBjOwogICAgd2hpbGUgKChjID0gZ2V0Y2hhcl91bmxvY2tlZCgpKSA8ICcwJykKICAgICAgICA7IC8vIGp1c3QgdG8gYmUgc2FmZQogICAgZm9yICgqcCA9IGMgLSAnMCc7IChjID0gZ2V0Y2hhcl91bmxvY2tlZCgpKSA+PSAnMCc7ICpwID0gKnAgKiAxMCArIGMgLSAnMCcpCiAgICAgICAgOwp9CnNpZ25lZCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgaW50IG4sIG07CiAgICBzY2FuX2ludCgmbiksIHNjYW5faW50KCZtKTsKICAgIC8vIGNpbiA+PiBuID4+IG07CiAgICBpbnQgcyA9IDEsIHQgPSBuOwogICAgc2Nhbl9pbnQoJnMpLCBzY2FuX2ludCgmdCk7CiAgICAvLyBjaW4gPj4gcyA+PiB0OwogICAgZm9yIChpbnQgaSA9IDAsIHUsIHYsIGY7IGkgPCBtOyArK2kpIHsKICAgICAgICBzY2FuX2ludCgmdSksIHNjYW5faW50KCZ2KSwgc2Nhbl9pbnQoJmYpOwogICAgICAgIC8vIGNpbiA+PiB1ID4+IHYgPj4gZjsKICAgICAgICBobHBwLmFkZEVkZ2UodSwgdiwgZiwgdHJ1ZSk7CiAgICB9CiAgICBobHBwLnMgPSBzLCBobHBwLnQgPSB0OwogICAgY291dCA8PCBobHBwLmNhbGMobikgPDwgZW5kbDsKfQo=