[Algorithm][다익스트라]

 

"""
시간복잡도 :
최단 거리 테이블에서 가장 짧은 거리의 노드를 매번 탐색.
해당 노드와 연결된 노드를 또 탐색.
=> V = 노드의 개수, O(V^2)

* 노드의 개수가 만개 이상이라면, 다른 개선된 알고리즘을 사용해야 한다. 


"""

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

# 최단 거리 테이블(distance)에서 거리가 가장 짧은 노드 탐색
def get_smallest_node():
    min_val = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_val and not visited[i]:
            min_val = distance[i]
            index = i
    return index

def dijkstra(start):
    distance[start]=0
    visited[start]=True
    for b,c in graph[start]:
        distance[b]=c
    
    for _ in range(n-1):
        now = get_smallest_node()
        visited[now]=True
        for b,c in graph[now]:
            distance[b]=min(distance[b], distance[now]+c)

dijkstra(start)

for i in range(1, n+1):
    if distance[i]==INF:
        print("INF")
    else:
        print(distance[i])

 

 

+ 개선 : 우선순위 큐

"""
우선순위 큐를 이용하여 시간복잡도 개선!

1. 노드 선택 및 큐 삽입/제거 : O(V logV)
2. 간선 처리 및 거리 갱신 : O(E logV)
=> O((V+E)logV) 

* 최악의 경우
E가 V보다 클 때, O(E log V)로 간주할 수 있다.

"""

import sys
import heapq ##우선순위 큐
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n+1)]
#(제거) visited = [False] * (n+1)
distance = [INF] * (n+1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

# 최단 거리 테이블(distance)에서 거리가 가장 짧은 노드 탐색 #### 개선!
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start]=0
    while q:
        dist, now = heapq.heappop(q) # 우선순위 큐 : 가장 작은 거 pop => 시간복잡도 O(logV)
        if distance[now] < dist: #### 이미 처리된 적이 있다면 넘어감
            continue 

        for b,c in graph[now]: # 간선의 개수 E => 시간복잡도 O(E)
            cost = dist + c
            if cost < distance[b]:
                distance[b] = cost
                heapq.heappush(q, (cost, b)) # => 시간복잡도 O(log V)

dijkstra(start)

for i in range(1, n+1):
    if distance[i]==INF:
        print("INF")
    else:
        print(distance[i])