import sys INF = sys.maxsize # 노드의 개수, 간선 갯수, 시작 정점 n, m, s = map(int, input().split()) g = [None] * n # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 visited = [False] * n D = [INF] * n # 최단 거리 테이블을 모두 무한으로 초기화 D[s] = 0 previous = [None] * n # 최단경로 기록을 위한 list previous[s] = s # 시작정점의 경로 초기화 # 모든 간선 정보를 입력받기 (0~n-1입력입니다. 1~n 입력이면 테이블들 n+1로 초기화했었어야함) for _ in range(m): a, b, c = map(int, input().split()) # a번 ..