#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=6*1e5+10;
struct node{
    int v,w;
};
int n,m,x,y,k,u,v,w,s;
vector<node> g[MAXN];
int vis[MAXN],cnt[MAXN],d[MAXN];

void spfa(){
    queue<int> q;
    memset(d,INF,sizeof d);
    d[s]=0;
    vis[s]=1;
    q.push(s);
    while(q.size()){
        u=q.front();
        vis[u]=0;
        q.pop();
        for(int i=0;i<g[u].size();i++){
            v=g[u][i].v;w=g[u][i].w;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(++cnt[v]>n)return;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>k;
        g[x].push_back({y,k});
    }
    spfa();
    for(int i=1;i<=n;i++){
        cout<<d[i]<<" ";
    }
    return 0;
}