"""
p, 230~ 232
(다익스트라 알고리즘) --> 기본적으로 "그리디" 알고리즘으로 분류

< 알고리즘 원리 >

1. [ 출발 노드 ]를 설정
2. [ 최단 거리 테이블 ]을 초기화
3. [ 방문하지 않은 노드 중 ]에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 "최단 거리 테이블을 갱신" --> '그리디'로 볼수 있음
5. < 위 과정에서 [ 3과 4번을 반복. ]>

- 각 노드에 대한 현재까지의 [ 최단 거리 정보를 ] 
  항상 " 1차원 리스트에 저장 "하며 [ 리스트를 계속 갱신 ]한다는 "특징".

- 매번 현재 처리하고 있는 노드(지역)을 기준으로 "주변 간선"을 확인
  나중에 [ 현재 처리하고 있는 노드 ]와 인접한 노드로 도달하는 [ 더 짧은 경로가 있으면 ]
  최단 거리 테이블을 갱신.
  
< 다익스트라 알고리즘을 구현하는 방법 2가지 >
방법 1. 구현하기 "쉽지만" [ 느리게 동작 ]하는 코드
방법 2. 구현하기에 조금 " 더 까다롭지만 "[ 빠르게 동작 ]하는 코드
 
--> 시험을 준비한다면 [ 방법 2 ]를 정확히 이해하고 구현할 수 있을 때까지 연습!
"""
# 책 정답 9-1.py (p, 237) 
# 아래 방법은 [ 전체 노드의 개수가 ** 5,000개 이하** ]라면 일반적으로 이 코드로 문제를 풀 수 있을것.
import sys
input = sys.stdin.readline # 입력을 "빠르게 동작"하는 방법(입력되는 데이터 수가 많을경우).
INF = int(1e9) # "무한"을 의미하는 값으로 "10억을" 설정

# [ 노드 ]의 개수, [ 간선 ]의 개수를 입력받기
n, m = map(int, input().split())

# [ 시작 노드 번호( "출발" 노드 ) ]를 입력받기
start = int(input())

# " 각 노드에 연결 "되어 있는 [ 노드에 대한 정보를 담는 리스트 ]를 만들기
graph = [[] for i in range(n + 1)]

# [ 방문한 적이 있는지 체크 ]하는 목적의 리스트를 만들기
visited = [False] * (n + 1)

# "최단 거리 테이블"을 [ 모두 무한 ]으로 초기화
distance = [INF] * (n + 1)

# 모든 [ ** 간선 정보 ** ]를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # [ a번 노드 ]에서 b번 노드로 가는 [ 비용이 'c'라는 의미 ]
    graph[a].append((b, c))

# " 방문하지 않은 노드 " 중에서, 가장 [ 최단 거리가 짧은 노드의 번호 ]를 반환
def get_smallest_node():
    min_value = INF # 가장 작은 값을 [ 무한 ]으로 초기화 설정.
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]: # 방문하지 않은경우.
            min_value = distance[i] #  min_value의 값을 [ 최단 거리가 짧은 노드의 ] 비용으로 바꿈.
            index = i
    return index

def dijkstra(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0 # [ 최단 거리 ]테이블 [출발노드] 거리값을 0으로 설정.
    visited[start] = True  # 방문 처리.
    
    for j in graph[start]:
        distance[j[0]] = j[1]
        
    # [ 시작 노드를 제외 ]한 전체 n - 1개의 노드에 대해 반복
    for i in range(n - 1):
        # 현재 최단 거리가 [ 가장 짧은 노드를 꺼내서 ], 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1] # 거리가 짧은 노드(비용) + 해당노드로 가는 비용 

     #[ 현재 노드를 거쳐서 ] 다른 노드로 이동하는 거리가
     # 현재 [ 최단 거리테이블에 있는 거리의 비용 ]보다 [ 더 짧은 경우의 조건문 ]
     # ex) '3번 노드' 방문의 비용이 '5'인데 출발 노드에서 [ 4번노드를 ** 거쳐서 ** ] 
     # '3번 노드 방문이 더 작을경우 ' 짧은 비용으로 갱신 시키는 과정.
            if cost < distance[j[0]]:
                distance[j[0]] = cost # 짧은 비용을 최단 거리테이블에 갱신.

# 다익스트라 알고리즘을 수행
dijkstra(start) # 출발 노드를 인수로 넘겨줌.

print(sep='\n' )
print("출력 ")

# 모든 노드로 가기 위한 최단 거리를 
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 [ 거리 ]를 출력
    else:
        print("[ 출발 노드 ]에서 "+ str([ i ]) +" 노드에 도달할수 있는 거리: " + str(distance[i]))