#include<iostream>
#include<queue>
using namespace std;
const int N=500005;
const int inf=2147483647;
struct node{
    int next,to,wei;
}e[N];
struct priority{
    long long ans;
    int id;
    bool operator <(const priority &x)const{
        return x.ans<ans;
    }
};
priority_queue<priority> q;
int head[N];
int cnt;
void adde(int u,int v,int w){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].wei=w;
    head[u]=cnt;
    return;
}
int dis[N];bool vis[N];
int main(){
    int n,m,s,u,v,w;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        adde(u,v,w);
    }
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    dis[s]=0;
    q.push((priority){0,s});
    while(!vis[q.empty()]){
        priority temp=q.top();
        q.pop();
        int u=temp.id;
        if(!vis[u]){
            vis[u]=true;
            for(int i=head[u];i>0;i=e[i].next){
                if(dis[u]+e[i].wei<dis[e[i].to])
                    dis[e[i].to]=dis[u]+e[i].wei,
                    q.push((priority){dis[e[i].to],e[i].to});
            }
        }
    }//int ans=0;
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}