#include <iostream>
#include<fstream>
#include<climits>
#include <cmath>
using namespace std;
struct nheap
{
    int dmin,k;
} heap[100001];
struct nod
{
    int inf,c;
    nod *next;
}*lv[100001],*p,*q;
int viz[100001],t[100001],idx[100001],rasp[100001];
ifstream fin("dijkstra.in");
ofstream fout ("dijkstr.out");
int main()
{
    int n,i,j,dmin,k,x,y,cost,m,s,nodc,f;
    const int infi=INT_MAX/2;
    fin>>n>>m>>s;
    for(i=1; i<=n; i++)
    {
        idx[i]=-1;
        rasp[i]=-1;
    }
    rasp[s]=0;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>cost;
        p=new nod;
        p->inf=y;
        p->c=cost;
        p->next=lv[x];
        lv[x]=p;
        p=new nod;
        p->inf=x;
        p->c=cost;
        p->next=lv[y];
        lv[y]=p;
    }
    viz[s]=1;
    int nh=0;
    for(nod *p=lv[s]; p; p=p->next)
    {
        t[p->inf]=s;
        nh++;
        idx[p->inf]=nh;
        heap[nh].dmin=p->c;
        heap[nh].k=p->inf;
        nodc=nh;
        while(nodc>1 && heap[nodc].dmin<heap[nodc/2].dmin)
        {
            swap(heap[nodc],heap[nodc/2]);
            swap(idx[heap[nodc].k],idx[heap[nodc/2].k]);
            nodc/=2;
        }
    }
    int kmin;
    while(nh)
    {
        kmin=heap[1].k;
        dmin=heap[1].dmin;
        rasp[kmin]=dmin;
        viz[kmin]=1;
        heap[1]=heap[nh--];
        idx[kmin]=-1;
        idx[heap[1].k]=1;
        nodc=1;
        while(1)
        {
            f=2*nodc;
            if(f>nh) break;
            if(f+1<=nh&&heap[f+1].dmin<heap[f].dmin) f++;
            if(heap[nodc].dmin<=heap[f].dmin) break;
            swap(heap[nodc],heap[f]);
            swap(idx[heap[nodc].k],idx[heap[f].k]);
            nodc=f;
        }
        for(p=lv[kmin]; p; p=p->next)
            if(!viz[p->inf])
            {
                nodc=0;
                if(idx[p->inf]==-1)
                {
                    nh++;
                    heap[nh].dmin=dmin+p->c;
                    heap[nh].k=p->inf;
                    idx[p->inf]=nh;
                    nodc=nh;
                }
                else if(dmin+p->c<heap[idx[p->inf]].dmin)
                {
                    heap[idx[p->inf]].dmin=dmin+p->c;
                    nodc=idx[p->inf];
                }
                while(nodc>1 && heap[nodc].dmin<heap[nodc/2].dmin)
                {
                    swap(heap[nodc],heap[nodc/2]);
                    swap(idx[heap[nodc].k],idx[heap[nodc/2].k]);
                    nodc/=2;
                }
            }
    }
    for(i=1; i<=n; i++) fout<<rasp[i]<<" ";
    return 0;
}