//最短路 dijkstral

#include<bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int maxn = ;

const ll INF = ;

typedef pair<ll ,int> pli;

struct node

{

    int to,cost;

    node(int t,int c):to(t),cost(c){}

    bool operator < (const node & a)const {

        return cost > a.cost;

    }

};

vector<node> E[maxn];

ll d[maxn];

priority_queue<pli,vector<pli>,greater<pli> > Q;

int main()

{

    int n,m,st;

    cin>> n>>m>>st;

    for(int i=;i<=m;i++)

    {

        int x,y,v;

        scanf("%d %d %d",&x, &y ,&v);

        E[x].push_back({y,v});

    }

    for(int i=;i<=n;i++)

    {

        d[i]=INF;

    }

    d[st] = ;

    Q.push({,st});

    while ( Q.size() )

    {

        pli now = Q.top();Q.pop();

        ll cost = now.first;

        int p=now.second;

        if(cost >= INF)

            continue;

        for(int i=;i<E[p].size();i++)

        {

            int v = E[p][i].to;

            if(d[v] > cost + E[p][i].cost)

            {

                d[v] = cost + E[p][i].cost;//更新最短路；

                Q.push({d[v],v});

            }

        }

    }

    for(int i=;i<=n;i++)

    {

        if(i!= n)

            cout<<d[i]<<" ";

        else

            cout<<d[i];

    }

    cout<<endl;

}