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(goal, left, predecessors, successors):

    #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()

        #Create a successor set
        successors[current] = {}
        
        #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:
                    predecessors[neighbor] = queue.Queue()
                    left.put(neighbor) #Add neighbor to visit-list
                    
                #Add path current->neighbor (unless start node)
                if predecessors[neighbor] is not None:
                    predecessors[neighbor].put(current)
                    successors[current][neighbor] = True

    #If goal was found, return path, and list of unvisited vertices
    #Otherwise (None, None)
    if goal in predecessors:
        return (left, predecessors, successors)
    else:
        return (None, None, None)

#Edits the graph by reversing the used amount of capacity of the edges
def reverse_routes(goal, predecessors, successors):
    
    routes = 10**9 #maximum speed
    route_from_start = [] #path from start to finish

    #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].get() #Get/Remove first path to current.
    route_from_start.append(current)

    while previous is not None:
        routes = min(routes, connections[previous][current])
        current = previous
        previouses = predecessors[current]
        #Get/Remove first path to current or get None
        if previouses is not None:
            previous = previouses.get()
        else:
            previous = None 
        route_from_start.append(current)

    #Reverse directions by used capacity
    current = route_from_start.pop()
    
    while len(route_from_start) > 0:
        nex = route_from_start.pop()
        connections[current][nex] -= routes
        connections[nex][current] += routes
        """
        if not path[nex].empty():
            #BALBALBALABAL
        """
        current = nex
        
    return routes


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

#Initialize list of predeccors and successors
predecessors = {1: None}
successors = {}

#Initialize total capacity count
routes = 0

#Continue until no new path is found
while predecessors is not None:
    #print(routes)

    #DEBUG
    left = queue.Queue()
    left.put(1)
    predecessors = {1: None}
    successors = {}

    #Call BFS
    left, predecessors, successors = bfs(n, left, predecessors, successors)

    #If path was found, add the new count and edit the graph
    if predecessors is not None:
        new_routes = reverse_routes(n, predecessors, successors)
        routes += new_routes


#Print answer:
print(routes)

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