import heapq
import sys
input = sys.stdin.readline
# heapq의 메서드들   heapq.heappush
# heap.heappop
# heap.heapify(list)
INF = int(1e9)
# 노드의 수와 간선의 수 입력받
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n+1)]
distance = [INF]*(n+1)


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


def dijkstra(start):
    distance[start] = 0
    q = [(0,start)]

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)