#include <bits/stdc++.h>
#define size 250001
#define infinity 0x7ffffff
#define pairintint pair<int,int>
using namespace std;
int n,m,s,d[size];
map<pair<int,int>,int> all;
vector<int> start[size];
void link(int from,int to,int dist){
    start[from].push_back(to);
    all[(pairintint){from,to}]=dist;
};
void SSSP(){
    for(int i=1;i<=n;i++) d[i]=(i==s)?0:infinity;
    bool mark[size]={};
    for(int i=1;i<=n;i++){
        int from=0,minn=infinity;
        for(int j=1;j<=n;j++){
            if(minn>d[j] && !mark[j]) minn=d[from=j]; //玄学赋值
        }
        mark[from]=true;
        for(auto to:start[from]){
            d[to]=min(d[to],d[from]+all[(pairintint){from,to}]);
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,d;
        cin>>u>>v>>d;
        link(u,v,d);
    }
    SSSP();
    for(int i=1;i<=n;i++){
        cout<<d[i]<<" ";
    }
    return 0;
}