#include<bits/stdc++.h>
using namespace std;
int book[1001],e[1001][1001],dis[1001];
int i,j,n,m,inf=99999999,t1,t2,t3,s,f,u,miin;
int main(){

    cin>>n>>m>>s;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(i==j) e[i][j]=0;
             else e[i][j]=inf;
        }
    }//chushi
    for(j=1;j<=m;j++){
            cin>>t1>>t2>>t3;
            e[t1][t2]=t3;
    }//durubian
    for(i=1;i<=n;i++){
        dis[i]=e[s][i];
    }//dischushihua
    for(i=1;i<=n;i++){
        book[i]=0;
    }//chushihuabook
    book[s]=1;
    for(i=1;i<n;i++){
         miin=inf;
         for(j=1;j<=n;j++){
            if (book[j]==0&&dis[j]<miin) miin=dis[j];u=j;
             }
             book[u]=1;
             for(j=1;j<=n;j++){
                if(e[u][j]+dis[u]<dis[j]&&e[u][j]<inf)//联通
                {
                    dis[j]=dis[u]+e[u][j]; 
                } 
             }

    }
    for(i=1;i<=n;i++) {
        cout<<dis[i]<<' ';
    }

    return 0;
}