#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;
}