52分

try:
    import Queue as pq
except ImportError:
    import queue as pq
N = int(1e5 + 5)
M = int(2e5 + 5)
INF = 0x3F3F3F3F
class qxx:
    def __init__(self):
        self.nex = 0
        self.t = 0
        self.v = 0
e = [qxx() for i in range(M)]
h = [0 for i in range(N)]
cnt = 0
dist = [INF for i in range(N)]
q = pq.PriorityQueue()
def add_path(f, t, v):
    global cnt, e, h
    cnt += 1
    e[cnt].nex = h[f]
    e[cnt].t = t
    e[cnt].v = v
    h[f] = cnt
def nextedgeid(u):
    i = h[u]
    while i:
        yield i
        i = e[i].nex
def dijkstra(s):
    dist[s] = 0
    q.put((0, s))
    while not q.empty():
        u = q.get()
        if dist[u[1]] < u[0]:
            continue
        for i in nextedgeid(u[1]):
            v = e[i].t
            w = e[i].v
            if dist[v] <= dist[u[1]] + w:
                continue
            dist[v] = dist[u[1]] + w
            q.put((dist[v], v))
if __name__ == "__main__":
    n, m, s = map(int, input().split())
    for i in range(m):
        u, v, w = map(int, input().split())
        add_path(u, v, w)
    dijkstra(s)
    for i in range(1, n + 1):
        print("{}".format(dist[i]), end=" ")
    print()