#include<bits/stdc++.h>
#include<queue>
using namespace std;

const int maxw=2e31-1;

int n,m,s;

struct code{
    int to,w;
};

queue<code> a[10001];
queue<int> p;


void work(int x,int dis[],bool b[])
{
    code k;
    bool t[n+1]={0};
    while(!a[x].empty()){
        k=a[x].front();a[x].pop();
        if(b[k.to]) continue;
        if(!t[k.to]){
            p.push(k.to);t[k.to]=1;
        }
        dis[k.to]=min(dis[k.to],dis[x]+k.w);
    }
    b[x]=1;
    if(p.empty()) return;
    int v=p.front();p.pop();
    work(v,dis,b);
}

int main()
{
    cin>>n>>m>>s;
    int dis[n+1],i,r;
    bool b[n+1]={0};
    code k;

    for(i=1;i<=n;i++) dis[i]=maxw;
    dis[s]=0;

    for(i=0;i<m;i++){
        cin>>r>>k.to>>k.w;
        if(r==k.to) continue;
        a[r].push(k);
    }
    work(s,dis,b);
    for(i=1;i<=n;i++) cout<<dis[i]<<" ";
    cin>>n;
    return 0;
}