Shared code

from __future__ import annotations
from collections import defaultdict

import sys

get_int = [int(x) for x in sys.stdin.buffer.read().split()]


t = 0
n, m = get_int[t], get_int[t+1]
t += 2
graph: list[dict[int, int]] = [defaultdict(int) for _ in range(n)]
capacities: list[dict[int, int]] = [defaultdict(int) for _ in range(n)]
for _ in range(m):
    u, v, w = get_int[t]-1, get_int[t+1]-1, get_int[t+2]
    t += 3
    graph[u][v] = 0
    capacities[u][v] += w
source, sink = 0, n-1

ans: int = 0
while True:
    # Run DFS to find shortest s-t path
    parent: list[int] = [-1] * n
    parent[source] = -2
    stack: list[tuple[int, int]] = [(source, 10 ** 18)]
    while stack:
        u, flow = stack.pop()
        for v in graph[u]:
            if parent[v] == -1 and capacities[u][v] > graph[u][v]:
                parent[v] = u
                if v == sink:
                    max_capacity = min(flow, capacities[u][v] - graph[u][v])
                    break
                stack.append((v, min(flow, capacities[u][v] - graph[u][v])))
    if parent[sink] == -1:
        # We didn't find au augmenting path
        break
    v = sink
    while v != source:
        graph[parent[v]][v] += max_capacity  # noqa
        graph[v][parent[v]] -= max_capacity  # noqa
        v = parent[v]
    ans += max_capacity

print(ans)