import sys

input_data = sys.stdin.read().split()
N = int(input_data[0])
M = int(input_data[1])
K = int(input_data[2])
S = int(input_data[3]) - 1
edges = []
ptr = 4
for _ in range(M):
    u = int(input_data[ptr]) - 1
    v = int(input_data[ptr+1]) - 1
    w = int(input_data[ptr+2])
    edges.append((u, v, w))
    ptr += 3
INF = 10**15
dp = [INF] * N
dp[S] = 0
for _ in range(K):
    next_dp = [INF] * N
    for u, v, w in edges:
        if dp[u] != INF:
            if dp[u] + w < next_dp[v]:
                next_dp[v] = dp[u] + w
    dp = next_dp
res = []
for val in dp:
    if val == INF:
        res.append("-1")
    else:
        res.append(str(val))
print("\n".join(res))