#include<iostream>
#include<cstring>
#include<climits>
using namespace std;
const int N = 1e4 + 10,M = 5e5 + 10;
int n,m,s,idx;
int h[N],e[M],w[M],ne[M],dist[N],vis[N];
void add(int a,int b,int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
    return;
}
void dijkstra(){
    for(int i = 1;i <= n;i++) dist[i] = INT_MAX;
    dist[s] = 0;
    for(int i = 1;i <= n;i++){
        int t = -1;
        for(int j = 1;j <= n;j++){
            if(!vis[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        vis[t] = true;
        for(int j = h[t];j != -1;j = ne[j]){
            int k = e[j];
            dist[k] = min(dist[k],dist[t] + w[j]);
        }
    }
    for(int i = 1;i <= n;i++) printf("%d ",dist[i]);
    return;
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    memset(h,-1,sizeof h);
    for(int i = 0;i < m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    dijkstra();
    return 0;
}