Shortest Routes I

import heapq

n, m = [int(x) for x in input().split()]

matrice = {i:[] for i in range(n)}
for _ in range(m):
    a,b,c = [int(x) for x in input().split()]
    matrice[a-1].append((b-1,c))

distance = [float('inf') for _ in range(n)]
distance[0] = 0
visited = set()
priority_queue = []
heapq.heappush(priority_queue, (0, 0))

while len(priority_queue) > 0:
    actual_node = heapq.heappop(priority_queue)[1]
    if actual_node in visited:
        continue
    visited.add(actual_node)
    for next_node, dist in matrice[actual_node]:
        prev_val = distance[next_node]
        distance[next_node] = min(distance[next_node], distance[actual_node] + dist)
        if distance[next_node] != prev_val:
            heapq.heappush(priority_queue, (distance[next_node], next_node))

for elt in distance:
    print(elt, end=' ')

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