#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
#define inf 10000000
#define Nmax 500050
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector< pair <int,int > > v[Nmax];
int n,m,p,x,y,z,d[Nmax];
bool incoada[Nmax];
void citeste()
{
    fin>>n>>m>>p;
    for(int i=1;i<=m;i++)
    {fin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

}
struct compara
{
    bool operator()(int x,int y)
    {
        return d[x]>d[y];
    }
};
priority_queue< int,vector<int>,compara>coada;

void Dijkstra(int s)
{
    for(int i=1; i<=n; i++)
        d[i]=inf;
    d[s]=0;
    coada.push(s);
    incoada[s]=true;
    while(!coada.empty())
    {
        int nodcurent=coada.top();
         coada.pop();
        for(size_t i=0; i<v[nodcurent].size(); i++)
        {
            int vecin=v[nodcurent][i].first;

            int cost=v[nodcurent][i].second;
            if(d[nodcurent]+cost<d[vecin])
            {
                d[vecin]=d[nodcurent]+cost;
                coada.push(vecin);
                if(incoada[vecin]==false)
                    incoada[vecin]=true;
            }
        }

    }
}
void afisare()
{
    for(int i=1;i<=n;i++)
        if(d[i]==inf)
        fout<<-1<<" ";
    else
        fout<<d[i]<<" ";
}
int main()
{
    citeste();
    Dijkstra(p);
    afisare();
}