"""Dinic's maximum flow algorithm (integer capacities).

Correctness hinges on three invariants:
  1. BFS builds a level graph from s using only edges with residual > 0.
  2. DFS sends blocking flow respecting levels (level[v] + 1 == level[u]
     along an edge).
  3. Current-arc (iter) pointers skip saturated edges within a phase.

Verified against brute-force (Edmonds-Karp / Ford-Fulkerson) on random
small graphs including multi-edges, zero capacities, disconnected graphs.
"""
from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u, v, cap):
        # forward edge index; backward is its pair
        fwd = [v, cap, None]  # placeholder; store as dict-like list
        # We'll store edges as [to, cap, rev_index]
        fi = len(self.adj[u])
        bi = len(self.adj[v])
        self.adj[u].append([v, cap, bi])
        self.adj[v].append([u, 0, fi])
        return fi

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, _ in self.adj[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0

    def dfs(self, u, t, f):
        if u == t:
            return f
        for i in range(self.it[u], len(self.adj[u])):
            self.it[u] = i
            v, cap, rev = self.adj[u][i]
            if cap > 0 and self.level[v] == self.level[u] + 1:
                pushed = self.dfs(v, t, min(f, cap))
                if pushed > 0:
                    self.adj[u][i][1] -= pushed
                    self.adj[v][rev][1] += pushed
                    return pushed
        return 0

    def max_flow(self, s, t):
        flow = 0
        INF = 10 ** 18
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                pushed = self.dfs(s, t, INF)
                if pushed == 0:
                    break
                flow += pushed
        return flow


def max_flow(n, edges, s, t):
    """edges: list of (u, v, cap). Returns max flow value."""
    d = Dinic(n)
    for u, v, c in edges:
        d.add_edge(u, v, c)
    return d.max_flow(s, t)