#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=2147483647;
int n,m,s,cnt;
int dis[500010],h[500010],to[500010],nxt[500010],val[500010];
bool vis[500010];
void add(int a,int b,int c){
    to[++cnt]=b;
    val[cnt]=c;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
void dijkstra(){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    dis[s]=0;
    dis[0]=inf;
    while(true){
        int u=0;
        for(int i=1;i<=n;i++){
            if(!vis[i]&&dis[u]>dis[i]){
                u=i;
            }
        }
        if(u==0)break;
        vis[u]=1;
        for(int i=h[u];i;i=nxt[i]){
            if(dis[to[i]]>dis[u]+val[i]){
                dis[to[i]]=dis[u]+val[i];
            }
        }
    }
}
signed main(){
    cin>>n>>m>>s;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dijkstra();
    for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
    return 0;
}