using namespace std;
const int N=10001,M=540510;
int hd[N],ver[M],val[M],nxt[M],idx;
int n,m,dis[N],s,vis[N];
struct node {
    int v,u;
    bool operator<(const node &x)const{
        return v>x.v;
    }
};
priority_queue<node> q;
void add(int x,int y,int v){
    ver[++idx]=y;
    val[idx]=v;
    nxt[idx]=hd[x];
    hd[x]=idx;
}
void dijkstra (int s) { 
    q.push((node){0, s});
    while (q.size()) {
        int t=q.top().u;q.pop();
        if (vis[t]) continue;
        vis[t]=1;
        for (int i=hd[t];i;i=nxt[i]) {
            int y=ver[i];
            if (dis[y]>dis[t]+val[i]){
                dis[y] = dis[t]+val[i];
                q.push((node){dis[t]+val[i], y});
            }
        }
    }
}
int main () {
    cin>>n>>m>>s;
    
    for(int i=1;i<=m;i++){
        int x,y,v;
        cin>>x>>y>>v;
        add(x,y,v);
        
    }
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    dijkstra(s);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<" ";
        
    }
    return 0;
}