[백준 1753] 최단경로

from queue import PriorityQueue
import sys

def Dijkstra(G,sp):
    
    INF=float("inf")
    dist=[INF]
    prev=[0]
    Q=set()
    que=PriorityQueue()

    for i in range(1,n+1):
        if i==sp:
            dist.append(0)
        else:
            dist.append(INF)
        prev.append(0)
        Q.add(i)
        que.put((dist[i],i))

    while Q!=set():
        while True:
            temp_u=que.get()[1]
            if temp_u in Q:
                u=temp_u
                break
        Q.remove(u)
        for i in range(1,len(G[u])+1):
            alt=dist[u]+G[u][i-1][1]
            if alt<dist[G[u][i-1][0]]:
                dist[G[u][i-1][0]]=alt
                prev[G[u][i-1][0]]=u
                que.put((alt,G[u][i-1][0]))
    
    return dist,prev

n,m=map(int, sys.stdin.readline().split())
sp=int(sys.stdin.readline())

G=[[] for _ in range(n+1)]
for i in range(1,m+1):
    u,v,w=map(int, sys.stdin.readline().split())
    G[u].append((v,w))
    
D,P=map(list, Dijkstra(G,sp))
INF=float("inf")
for i in range(1,len(D)):
    if D[i]==INF:
        print("INF")
    else :
        print(D[i])

 

 

#이 문제를 통해 다익스트라 알고리즘이란 걸 처음 접했네요. 나무위키 참고 했습니다.