Shortest Routes I

import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate, groupby
from functools import lru_cache, cmp_to_key, reduce
from math import gcd, isqrt, comb, inf, pi, sqrt, atan2, hypot


def main():
    data = sys.stdin.buffer.read().split(); idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    # a = list(map(int, data[idx:idx + n])); idx += n
    # print(n,m)
    A, B, C = [], [], []
    adj = [[] for _ in range(n +1)]
    for _ in range(m):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        adj[a].append((b,c))


    # d = deque([(1,0)])
    h = [(0,1)] # heap : time, position

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


    while h:
        time, pos = heappop(h)
        if time >= out[pos]: continue
        out[pos] = time
        # print(out)

        for dest, cost in adj[pos]:
            if time + cost < out[dest]:
                heappush(h, (time + cost, dest))






    print(" ".join(map(str, out[1:])))
    # sys.stdout.write("\n".join(map(str, out[1:])) + "\n")


main()

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