Internet connection

import queue

#Read input
#n: number of nodes
#m: number of edges
n, m = [int(i) for i in input().split()]

#Read edge inputs and initialize edges
connections = {i: {} for i in range(1,n+1)}

for i in range(m):
    a,b,w = [int(i) for i in input().split()] #a->b with weigth w
    connections[a][b] = w
    if a not in connections[b]: #Always connect the other direction, with weigth 0
        connections[b][a] = 0

#Search for goal with Breadth-first-search
#Start from where left of when goal was found last time
def bfs(start, goal):

    #Initialize a queue for BFS with starting vertex
    left = queue.Queue()
    left.put(start)

    #Initialize list of predeccors
    predecessors = {start: None}

    #Continue until goal is found or there are no unvisited neighbors left
    while not left.empty() and goal not in predecessors:
        
        #Take first vertex from the "waiting line"
        current = left.get()
        
        #Go trough every neighbor with positive speed
        for neighbor, speed in connections[current].items():
            if speed > 0:
                
                #If predecessors to neighbor was not yet found
                if neighbor not in predecessors:
                    left.put(neighbor) #Add neighbor to visit-list
                    predecessors[neighbor] = current

    #If goal was found, return path
    return predecessors if goal in predecessors else None
    

#Edits the graph by reversing the used amount of capacity of the edges
def reverse_routes(goal, predecessors):
    
    routes = 10**9 #maximum speed

    #Get maximum capacity that can be used troughout a path
    #Start from goal and go back a step at a time until start is reach.
    current = goal
    previous = predecessors[current]

    while previous is not None:
        routes = min(routes, connections[previous][current])
        current = previous
        previous = predecessors[current]

    #Revert flows
    current = goal
    previous = predecessors[current]
    
    while previous is not None:
        connections[previous][current] -= routes
        connections[current][previous] += routes
        current = previous
        previous = predecessors[current]
        
    return routes


#Count the maximum flow from start to goal
def max_flow(start, goal):
    
    #Initialize total capacity count
    routes = 0

    #Continue until no new path is found
    while True:

        #Call BFS
        predecessors = bfs(start, goal)

        #If path was found, add the new count and edit the graph
        #Otherwise quit
        if predecessors is not None:
            new_routes = reverse_routes(goal, predecessors)
            routes += new_routes
        else:
            break

    return routes
    
#Print answer:
print(max_flow(1,n))

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