#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;

const int MAX = 2147483647;

struct line{
    int last,to,w;
}e[3000005];


struct node{
    int mm;
    int pos;
    bool operator <(const node &x)const
    {
        return x.mm<mm;
    }
};
priority_queue <node> q;
int dis[1000005];
bool vis[100005];int cnt;
int head[1000005];
void add_edge(int u,int v,int w){
    e[++cnt].last = head[u];
    e[cnt].to = v;
    e[cnt].w = w;
    head[u] = cnt;
}

int main(){
    int n,m,s;
    cin>>n>>m>>s;
    for(int i = 1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    for(int i = 1;i<=n;++i){
        dis[i] = MAX;
    }
    dis[s] = 0;vis[s] = 1;
    q.push((node){0,s});
    while(!q.empty()){
        node now = q.top();
        vis[now.pos] = 1;
        q.pop();
        for(int i = head[now.pos];i;i = e[i].last){
            if(!vis[e[i].to] && dis[e[i].to] > dis[now.pos] + e[i].w){
                dis[e[i].to] = dis[now.pos] + e[i].w;
                q.push((node){dis[e[i].to],e[i].to});
            }
        }
    }
    for(int i = 1;i<=n;++i){
        cout<<dis[i]<<" ";
    }
    return 0;
}