#include <fstream>

using namespace std;
ifstream f("date.in");
ofstream g("date.out");
struct nod{int nr;
int val;
nod *urm;};
nod *a[100],*p,*q;
int s[100],t[100],n,m,i,j,x,y,z,v,viz[100],nr,vf;
void pune(int x,int y,int z)
{
    p=new nod;
    p->nr=y;
    p->val=z;
    p->urm=0;
    if(!a[x])
        a[x]=p;
    else
    {
        q=a[x];
        while(q->urm)
            q=q->urm;
        q->urm=p;
    }
}
void afisare()
{
    for(i=1;i<=n;i++)
        g<<s[i]<<" ";
    g<<endl;
    for(i=1;i<=n;i++)
        g<<t[i]<<" ";
    g<<endl;

    for(i=1;i<=n;i++)
    {
        p=a[i];
        while(p)
        {
            g<<p->nr<<" "<<p->val<<endl;
            p=p->urm;
        }
        g<<endl;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        pune(x,y,z);
        pune(y,x,z);
    }
    f>>v;

    /*for(i=1;i<=n;i++)
    {
        p=a[i];
        while(p)
        {
            viz[p->nr]=1; ///pentru a verifica nodurile catre care nu exista muchie directa
            nr++;
            if(p->urm) p=p->urm;
            else break;
        }
        if(nr!=n)
        {
            for(j=1;j<=n;j++)
                if(!viz[j]&&j!=i) ///adaugam nodurile nevizitate, diferite de nodul i
                {
                    q=new nod;
                    q->nr=j; ///introducem nodul j cu lungimea drumului=99999
                    q->val=99999;
                    q->urm=0;
                    p->urm=q;
                    p=q;
                }
        }
        for(j=1;j<=n;j++)
            viz[j]=0;
        nr=0;
    }*/

    for(i=1;i<=n;i++)
        if(i!=v) s[i]=1;

    p=a[v];
    while(p)
       if(p->val!=99999) t[p->nr]=v,p=p->urm;
       else break;


    for(i=1;i<n;i++)
    {
        int s1,s2;
        int m=99999;
        p=a[v];
        while(p)
        {
            if(s[p->nr]&&p->val<m)
                m=p->val,vf=p->nr;
            p=p->urm;
        }
        s[vf]=0;

         q=a[v];
        while(q)
            {
                if(q->nr==vf) s1=q->val; ///s1=drumul de la nodul v la varful vf
                q=q->urm;
            }
        p=a[v];
        while(p)
        {
            if(s[p->nr])
            {
                q=a[vf];
                while(q)
                {
                    if(q->nr==p->nr) s2=q->val; ///s2=drumul de la varful vf la nodul X(ia valorile : 1,2,..,n)
                    q=q->urm;
                }
                if(p->val>s1+s2)
                    p->val=s1+s2,t[p->nr]=vf;
            }
            p=p->urm;
        }
    }

    p=a[v];
    while(p)
    {
        //g<<"Drumul minim de la "<<v<<" la "<<p->nr<<" este de "<<p->val<<endl;
        g<<p->val<<" ";
        p=p->urm;
    }
        return 0;
}