// 堆优化dijkstra 将距离起点最近的点 取出 用来更新其余的点
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n, m,s;
vector<pii> to[100001];
int dis[100001];
int main() {
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
to[u].push_back({w, v});
}
memset(dis, 0x7f, sizeof(dis));
dis[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [pre, u] = pq.top();
pq.pop();
if (pre > dis[u])
continue;
for (auto [cst, v] : to[u]) {
if (pre + cst < dis[v]) {
dis[v] = pre + cst;
pq.push({pre + cst, v});
}
}
}
for (int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
}