https://www.acmicpc.net/problem/1753
import heapq
import sys
input = sys.stdin.readline
v, e = map(int, input().split())
start = int(input())
graph = [[] for _ in range(v+1)]
INF = int(1e9)
distance = [INF] * (v+1)
for _ in range(e):
n, v, w = map(int, input().split())
graph[n].append((v, w))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, node = heapq.heappop(q) # dist-거리, node-위치
if distance[node] < dist:
continue
for next in graph[node]:
cost = distance[node] + next[1]
if cost < distance[next[0]]:
distance[next[0]] = cost
heapq.heappush(q, (cost, next[0]))
dijkstra(start)
for i in range(1, len(distance)):
if distance[i] == INF:
print('INF')
else:
print(distance[i])
다익스트라 알고리즘을 이용하여 풀면 된다.