#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 500005;
vector<P> g[maxn];
priority_queue<P, vector<P>, greater<P> > pq;
int n, m, s;
int vis[maxn], d[maxn];
int main(){
//freopen("D:\\DESKTOP\\测试样例\\P3371_2.in", "r", stdin);
scanf("%d%d%d", &n, &m, &s);
memset(d, INF, sizeof(d));
memset(vis, 0, sizeof(vis));
for(int i=1; i<=m; i++){
int t1, t2, t3;
scanf("%d%d%d", &t1, &t2, &t3);
g[t1].push_back(make_pair(t3, t2));
}
vis[s] = 1;
d[s] = 0;
for(int i=0; i<g[s].size(); i++){
d[g[s][i].second] = min(d[g[s][i].second], d[s]+g[s][i].first);
pq.push(g[s][i]);
}
while(!pq.empty()){
P now = pq.top();
pq.pop();
if(!vis[now.second]){
vis[now.second] = 1;
for(int i=0; i<g[now.second].size(); i++){
if(!vis[g[now.second][i].second]){
d[g[now.second][i].second] = min(d[g[now.second][i].second], d[now.second]+g[now.second][i].first);
pq.push(g[now.second][i]);
}
}
}
}
for(int i=1; i<=n; i++){
printf("%d ", d[i]);
}
return 0;
}