Shortest Routes I

# import heapq
from queue import PriorityQueue
from time import time
t0 = time()
cityCount, flightCount = [int(aa) for aa in input().strip().split(" ")]
flights = [tuple([int(aa) for aa in input().strip().split(" ")]) for _ in range(flightCount)]

# connMap = [[(end, tim) for start,end,tim in flights if (start == city)] for city in range(1,cityCount+1)]
# t0 = time()
connMap = [[] for city in range(cityCount)]
for start,end,cost in flights:
    connMap[start-1].append((end-1,cost))
    # connMap[end-1].append((start-1,cost))
# t1 = time()
# print(t1-t0)
# print(connMap)
# exit()
dists = [int(1E10) for _ in range(cityCount)]
dists[0] = 0
checked = [False for _ in range(cityCount)]

qq = PriorityQueue()
qq.put((0,0))
while not qq.empty():
    prio, city = qq.get()
    if (checked[city]): continue
    checked[city] = True
    for neighbor, cost in connMap[city]:
        if (dists[city] + cost < dists[neighbor]):
            dists[neighbor] = dists[city] + cost
            qq.put((-dists[neighbor], neighbor))
print(" ".join([str(aa) for aa in dists]))
t1 = time()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED