#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000
#define pll pair<int,int>
#define M 100001
using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
int n, x, y, c, start, m;
vector <pll> L[M];
priority_queue <pll, vector <pll>, greater<pll>> pq; //in varful cozii va fi mereu nodul nevizitat aflat la distanta minima fata de nodul curent
int d[M]; //distanta minima de la nodul de start la oricare alt nod
bool viz[M];


void citire()

{

    in >> n >> m >> start;

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

    {

        in >> x >> y >> c;

        L[x].push_back(make_pair(c, y));

        L[y].push_back(make_pair(c, x));

    }

}



void dijkstra(int start)

{

    for (int i=1; i<=n; i++) //initializare dmin gasita

        d[i]=INF;

    d[start]=0;

    pq.push(make_pair(0, start));



    while(!pq.empty())

    {

        int a=pq.top().second;

        int b=pq.top().first; //extragem din coada elementul umrator

        viz[a]=1;

        pq.pop();

        for (int i=0; i<L[a].size(); i++) //pt fiecare vecin

        {



            if (d[L[a][i].second]>b+L[a][i].first && viz[L[a][i].second]==0)

            {

                d[L[a][i].second]=b+L[a][i].first; //actualiam distanta minima gasita

                pq.push(make_pair(d[L[a][i].second], L[a][i].second)); //punem in coada pentru a continua parcurgerea din nodul vecin

            }

        }

    }

}



void afis()

{

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

    {

        if (d[i]==INF) //daca nu se poate ajunge la nodul i din start

            out << 0 << " ";

        else

            out << d[i] << " ";

    }

}



int main()

{

    citire();

    dijkstra(start);

    afis();

    return 0;

}