Shortest Routes I

import sys
import heapq
from collections import deque

input = sys.stdin.readline
INF = float("inf")

def I():  return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split())) 
def S():  return input().strip()                 

def read_graph(n, m, directed=True):
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b, *w = MI()
        adj[a].append((b, w[0]) if w else b)
        if not directed:
            adj[b].append((a, w[0]) if w else a)
    return adj

def dijkstra(adj, starts):
    if isinstance(starts, int):
        starts = [starts]

    dist = [INF] * len(adj)
    parent = [-1] * len(adj)
    pq = []
    for s in starts:
        dist[s] = 0
        pq.append((0, s))

    while pq:
        d, u = heapq.heappop(pq)

        if d != dist[u]:
            continue

        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u
                heapq.heappush(pq, (d + w, v))

    return dist, parent

n, m = MI()
adj = read_graph(n, m)

dist, _ = dijkstra(adj, 1)
print(" ".join(map(str, dist[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