#include "iostream"
#include "vector"
#include "cstring"

std::vector<std::pair<int,int>> paint[10005];
//first是终点，second是边权
int cost[10005];
bool isBlocked[10005];

int main(){
    memset(cost,0x3f3f3f,sizeof (cost));
    memset(isBlocked, false,sizeof (isBlocked));
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        paint[u].push_back({v,w});
    }
    cost[s]=0;
    for(int k=1;k<=n;k++){
        int min =1;
       for(int j=2;j<=n;++j){
           if(!isBlocked[j] && cost[j]<cost[min]){
               min=j;
           }
       }
       isBlocked[min]= true;
       for(int i=0;i<paint[min].size();i++){
           if(cost[paint[min][i].first]>cost[min]+cost[paint[min][i].second]){
               cost[paint[min][i].first]=cost[min]+cost[paint[min][i].second];
           }
       }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",cost[i]);
    }
}```