#include <bits/stdc++.h>
using namespace std;
struct EDGE {int v,y;};
vector<EDGE> e[1000009];int d[1000009];
set<pair<int,int>>q;
int main()
{
    int n,m,s,u1,v1,w1;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u1,&v1,&w1);
        EDGE t;
        t.y=v1;t.v=w1;
        e[u1].push_back(t);
    }
    memset(d,127,sizeof(d));
    d[s]=0;q.clear();
    for(int i=1;i<=n;++i){
        q.insert(make_pair(d[i],i));
    }
    for(;!q.empty();){
        int x=q.begin()->second;

        if(x==n||d[x]>1<<30)
            break;
        q.erase(q.begin());
        for(auto i:e[x]){
            if(d[x]+i.v<d[i.y]){
                q.erase(make_pair(d[i.v],i.y));
                d[i.y]=d[x]+i.v;
                q.insert(make_pair(d[i.v],i.y));
            }
        }
            }
        for(int i=1;i<=n;++i){
            cout<<d[i]<<" ";
        }
    return 0;
}