Shortest Routes I

import heapq

def main():
    n, m = [int(x) for x in input().split()]
    flight_connections = {i: {} for i in range(1, n+1)}
    
    for _ in range(m):
        a, b, c = [int(x) for x in input().split()]
        # Si hay múltiples vuelos entre las mismas ciudades, guardamos el más barato
        if b in flight_connections[a]:
            flight_connections[a][b] = min(flight_connections[a][b], c)
        else:
            flight_connections[a][b] = c

    # --- Algoritmo de Dijkstra desde el nodo 1 ---
    distances = {i: float('inf') for i in range(1, n+1)}
    distances[1] = 0
    
    # Cola de prioridad: almacena tuplas (distancia, nodo)
    pq = [(0, 1)]
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        # Si la distancia actual es mayor a la registrada, la ignoramos
        if current_dist > distances[u]:
            continue
            
        # Explorar vecinos
        for v, weight in flight_connections[u].items():
            distance = current_dist + weight
            
            if distance < distances[v]:
                distances[v] = distance
                heapq.heappush(pq, (distance, v))

    # Construimos la solución con las distancias desde el nodo 1 al resto
    sol = [distances[i] for i in range(1, n+1)]

    print(*sol)

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