dijkstra

import sys
import heapq
from collections import defaultdict

v,e = sys.stdin.readline().strip().split()

adj = defaultdict(list)
d = dict()
for _ in range(int(e)):
    u, v, w = sys.stdin.readline().strip().split()
    adj[u].append((v, int(w)))
    adj[v].append((u, int(w)))
    d[u] = float('inf')
    d[v] = float('inf')

s = sys.stdin.readline().strip()
d[s] = 0

def dijkstra(adj, d, s):
    q = [(d[s],s)]
    while q:
        pathlen, cur = heapq.heappop(q)
        for v,w in adj[cur]:
            if pathlen + w < d[v]:
                d[v] = pathlen + w
                heapq.heappush(q,(d[v],v))

dijkstra(adj,d, s)
print(d)