Internet connection

import sys


def find_way(neighbors, weights, s, t):
    q = list()
    q.append(s)
    visited = list()
    parents = dict()

    while q:
        c = q.pop(0)
        visited.append(c)
        for n in neighbors[c]:
            if weights[c][n] > 0:
                if n is t:
                    path = [t]
                    p = c
                    while p is not s:
                        path.append(p)
                        p = parents[p]
                    path.append(s)
                    return path
                if n not in visited:
                    parents[n] = c
                    q.append(n)
    return list()


def solve():
    [n, m] = sys.stdin.readline().split()
    n = int(n)
    m = int(m)
    neighbors = list()
    for i in range(n):
        neighbors.append(list())
    weights = dict()

    for i in range(m):
        line = sys.stdin.readline()
        a, b, c = [int(i) for i in line.split()]
        neighbors[a-1].append(b-1)
        neighbors[b-1].append(a - 1)
        if a-1 not in weights:
            weights[a-1] = dict()
        weights[a - 1][b - 1] = c

        if b-1 not in weights:
            weights[b-1] = dict()
        if a-1 not in weights[b-1]:
            weights[b - 1][a - 1] = 0

    total_c = 0
    while True:
        path = find_way(neighbors, weights, 0, n-1)
        if not path:
            print(total_c)
            return

        min_c = weights[path[1]][path[0]]
        for i in range(1, len(path)):
            if weights[path[i]][path[i-1]] < min_c:
                min_c = weights[path[i]][path[i-1]]
        total_c += min_c
        for i in range(1, len(path)):
            weights[path[i]][path[i-1]] -= min_c
            weights[path[i-1]][path[i]] += min_c

if __name__ == '__main__':
    solve()

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

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED