Shortest Routes I

import sys
import heapq
inp = sys.stdin.read().split()

n,m = int(inp[0]),int(inp[1])

adj = [[] for _ in range(n + 1)]

for i in range(m):
    frm = int(inp[2+3*i])
    to = int(inp[3+3*i])
    dst = int(inp[4+3*i])
    adj[frm].append((to,dst))


def dijkstra(n, adj, start_node):
    '''
    n is numer of nodes
    adj is an adjacency list
    start_node is the start node duh
    '''
    dist = [float("inf")]*(n+1) #make it 1 indexed (:)
    dist[start_node]=0
    pq = [(0,start_node)]
    #processed = [False]*(n+1) slower in python -> use lazhy deletion check

    while pq:
        #while priorirty queue still ahs elements
        curr_dist, curr_n = heapq.heappop(pq)
        if curr_dist > dist[curr_n] :
            continue
        '''if processed[curr_n] : continue
        processed[curr_n] = True'''

        for b,w in adj[curr_n]: #each neighbor of current node has b = neighbor node and w = distance to it
            if dist[curr_n] + w < dist[b] :
                dist[b]=  dist[curr_n] + w 
                heapq.heappush(pq,(dist[b],b))

    return dist[1:]


print(*dijkstra(n,adj,1))

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