#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,M = 1e6+10;
int h[N],e[M],nex[M],d[N],w[M],idx=1;
int n,m,s;
bool v[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;

void add(int a,int b,int c){
    e[idx] = b;
    w[idx] = c;
    nex[idx] = h[a];
    h[a] = idx++;
}
void dijkstra(){
    d[s] = 0;
    q.push({0,s});
    while(q.size()){
        auto t = q.top();
        q.pop();
        int dist = t.first,u = t.second;
        if(v[u]) continue;
        v[u] = 1;
        for(int i=h[u];i != -1;i=nex[i]){
            int j = e[i],k = w[i];
            if(d[j]>dist + k){
                d[j] = dist + k;
                    q.push({d[j],j});
            }   
        }
    }
}
int main(){
    cin>>n>>m>>s;
    
    memset(h,-1,sizeof(h));
    memset(d,0x3f3f3f3f,sizeof(d));
    memset(v,0,sizeof(v));

     for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        cout<<d[i]<<' ';
    }
    return 0;
}