#include<bits/stdc++.h>
using namespace std;
const int N=1e4+2;
const int inf=0x3f3f3f3f;
typedef long long ll;
int n,m,s,u,v,sum;
struct node{
    int to,val;
};
vector<vector<node> >edge;
int dis[N],vis[N];
void dijkstra(){
    dis[s]=0;
    for(int i=1;i<=n;i++){
        int t=inf,k=0;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&dis[j]<t){
                t=dis[j];
                k=j;
            }
        }    
        vis[k]=1;
        for(auto j:edge[k])if(!vis[j.to])dis[j.to]=min(dis[j.to],dis[k]+j.val);
    }
}
int main(){
    cin>>n>>m>>s;
    edge.resize(n+1);
    memset(dis,inf,sizeof(dis));
    for(int i=1;i<=m;i++){
        cin>>u>>v>>sum;
        edge[v].push_back({u,sum});
        edge[u].push_back({v,sum});
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(!vis[i])cout<<(1<<31)-1<<" ";//说明不相连
        else cout<<dis[i]<<" ";
    }
}