#include<bits/stdc++.h>
using namespace std;
struct edge{
    int v,w,nex;
}e[int(520131.4)];
int head[int(131452.0)],tot=0;
void add(int u,int v,int w){
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nex=head[u];
    head[u]=tot;
}
int n,m,s;
int dis[100010];
struct node
{
    int u,d;
    bool operator<(const node &x)const{
        return d>x.d;
    }
};
void ma(){
    int i;
    for(int i=1;i<=n;i++)dis[i]=(1ll<<25);
    dis[s]=0;
    priority_queue<node>Q;
    Q.push((node){s,0});
    while(!Q.empty()){
        node f=Q.top();
        Q.pop();
        int u=f.u,d=f.d;
        if(d!=dis[u])continue;
        for(i=head[u];i;i=e[i].nex);
        {
            int v=e[i].v,w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                Q.push((node){v,dis[v]});
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    int x,y,z;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
    }
    ma();
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
}