#include <bits/stdc++.h>
constexpr int inf=2147483647;
using namespace std;
int dis[100005],vis[100005],n,m,s;
struct edge{
    int v,w;
    bool operator<(const edge e2)const{
        return w>e2.w;
    }
};
vector <edge> e[100005];
void Dijkstra_Optimize(int s){
    for (int i=0;i<=n;i++){
        dis[i]=inf;
    }
    dis[s]=0;
    priority_queue<edge> pq;
    pq.push((edge){s,0});
    while(!pq.empty()){
        int u=pq.top().v;
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for (auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                pq.push((edge){v,dis[v]});
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
    }
    Dijkstra_Optimize(s);
    for (int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
}