#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int viz[100002],n,m,p,nc,L[500002],vec[500002],urm[500002],k,H[100002],poz[100002];
long long cost[100002],dist[500002],Min;
const long long I=5000000001;

void add(int x1, int x2, int x3)
{
    k++;
    vec[k]=x2;
    dist[k]=x3;
    urm[k]=L[x1];
    L[x1]=k;
}

int father(int nc)
{
    return nc/2;
}

int lson(int nc)
{
    return 2*nc;
}

int rson(int nc)
{
    return 2*nc+1;
}

void heap_down(int nc, int N) //sift
{
    int son;
    do
    {
        son=0;
        if (lson(nc)<=N)
        {
            son=lson(nc);
            if (rson(nc)<=N and H[rson(nc)]<H[son])
                son=rson(nc);
            if (H[son]>=H[nc])
                son=0;
        }
        if (son)
        {
            swap(poz[H[son]],poz[H[nc]]);
            swap(H[son],H[nc]);
            nc=son;
        }
    }while (son);
}

void heap_up(int nc) //percolate
{
    int aux=H[nc],paux=poz[H[nc]];
    while (nc>1 and aux<H[father(nc)])
    {
        poz[H[nc]]=poz[H[father(nc)]];
        H[nc]=H[father(nc)];
        nc=father(nc);
    }
    poz[nc]=paux;
    H[nc]=aux;
}

int main()
{
    int i,j,tz,x1,x2,x3,z;
    f >> n >> m >> p;
    for (i=1;i<=m;i++)
    {
        f >> x1 >> x2 >> x3;
        add(x1,x2,x3);
        add(x2,x1,x3);
    }
    for (i=1;i<=n;i++)
    {
        cost[i]=I;
        poz[i]=i;
        H[i]=i;
    }
    cost[p]=0;
    swap(H[1],H[p]);
    swap(poz[1],poz[p]);
    k=n;
    while (k)
    {
        nc=H[1];
        swap(poz[H[1]],poz[H[k]]);
        swap(H[1],H[k]);
        k--;
        heap_down(1,k);
        z=L[nc];
        //g << nc << ' ';
        while (z)
        {
            if (cost[vec[z]]>cost[nc]+dist[z])
            {
                cost[vec[z]]=cost[nc]+dist[z];
                heap_up(poz[vec[z]]);
            }
            z=urm[z];
        }
    }
    for (i=1;i<=n;i++)
        if (cost[i]==I)
            g << -1 << ' ';
        else
            g << cost[i] << ' ';
    return 0;
}