Download Speed

import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate, groupby
from functools import lru_cache, cmp_to_key, reduce
from math import gcd, isqrt, comb, inf, pi, sqrt, atan2, hypot


def main():
    data = sys.stdin.buffer.read().split(); idx = 0
    # n = int(data[idx]); idx += 1
    n, m = map(int, data[idx:idx + 2]); idx += 2
    # a = list(map(int, data[idx:idx + n])); idx += n
    # s = data[idx].decode(); idx += 1                  # strings


    adj = [[] for _ in range(n + 1)]
    cap = [[0] * (n + 1) for _ in range(n + 1)]
    for _ in range(m):
        a, b, c = map(int, data[idx:idx + 3]); idx += 3
        cap[a][b] += c
        adj[a].append(b)
        adj[b].append(a)

    total = 0
    while n > 1:
        fromm = [0] * (n + 1)
        fromm[1] = 1
        # dq = deque([1])
        # while dq and not fromm[n]:
        #     u = dq.popleft()
        #     for v in adj[u]:
        #         if not fromm[v] and cap[u][v] > 0:
        #             fromm[v] = u
        #             dq.append(v)


        q = [1]
        for u in q:  
            for v in adj[u]:
                if not fromm[v] and cap[u][v] > 0:
                    fromm[v] = u
                    q.append(v)

        if not fromm[n]:
            break



        path = []
        v = n
        while v != 1:
            path.append((fromm[v], v))
            v = fromm[v]
        f = min(cap[u][v] for u, v in path)
        
        for u, v in path:
            cap[u][v] -= f
            cap[v][u] += f
        total += f



        # f = 10**9
        # v = n
        # while v != 1:
        #     f = min(f, cap[fromm[v]][v])
        #     v = fromm[v]
        # v = n
        # while v != 1:
        #     cap[fromm[v]][v] -= f
        #     cap[v][fromm[v]] += f
        #     v = fromm[v]

        # total += f
    print(total)

    # sys.stdout.write("\n".join(map(str, out)) + "\n")  # one value per line


main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED