#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct edge{
    int v,w;
};
vector<edge> g[10010];
int dis[10010];
int inqueue[10010];
void spfa(){
    for(int i=1;i<=n;++i) dis[i]=2147483647;
    dis[s]=0;
    queue<int> q;
    q.push(s);
    inqueue[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inqueue[u]=0;
        for(int i=0;i<g[u].size();++i){
            edge tmp=g[u][i];
            int v=tmp.v,w=tmp.w;
            if(dis[v]>dis[u]+dis[w]) {
                dis[v]=dis[u]+dis[w];
                if(inqueue[v]==0){
                    q.push(v);
                    inqueue[v]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;++i) cout<<dis[i]<<' ';
    cout<<endl;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    spfa();
    return 0;
}