#include "cstdio"
#include "vector"
#define fin "dijkstra.in"
#define fout "dijkstra.out"
#define inf 0x3f3f3f3f
using namespace std;

    int heap[1024],dpt,viz[1024];

    typedef struct drum { int x,c; };
    int n,m,first,d[1024];
    vector<drum> G[1024];


void citire() // citire ?!
{
    freopen(fin,"r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        drum d; d.x=y; d.c=z;
        G[x].push_back(d);
    }
    scanf("%d",&first);
    fclose(stdin);
}

void push(int x)
{
    dpt++;
    int poz=dpt;
    heap[dpt]=x;
    int padre = (poz-poz%2)/2;
    while (d[heap[padre]]>d[heap[poz]] && poz != 1)
    {
        int aux=heap[padre]; heap[padre]=heap[poz]; heap[poz]=aux;
        poz=padre;
        padre = (poz-poz%2)/2;
    }
}

int pop()
{
    int rez=heap[1];
    heap[1]=heap[dpt--];
    int nod=1;
    int son = d[heap[2]]>d[heap[3]] ? 3:2;
    while(d[heap[nod]]>d[heap[son]] && nod <dpt)
    {
        int aux=heap[nod]; heap[nod]=heap[son]; heap[son]=aux;
        nod=son;
        son = d[heap[2*nod]]<d[heap[2*nod+1]] ? 2*nod:2*nod+1;
    }
    return rez;
}

void decrease(int x)
{
    int poz;
    for (int i=1;i<dpt && heap[i]!=x;i++,poz=i);
    int padre = (poz-poz%2)/2;
    while (d[heap[padre]]>d[heap[poz]] && poz != 1)
    {
        int aux=heap[padre]; heap[padre]=heap[poz]; heap[poz]=aux;
        poz=padre;
        padre = (poz-poz%2)/2;
    }
}

void build_heap()
{
    for (int i=1;i<=n;i++)
        d[i]=inf;
    for (vector<drum>::iterator it = G[first].begin(); it != G[first].end(); it ++)
        d[it->x]=it->c;
    for (int i=1;i<=n;i++)
        if (i!=first)
            push(i);
}

void dijkstra() // Dijkstra
{
    while (dpt) // cat timp mai avem varfuri in heap
    {
        int vs=pop();
        for (vector<drum>::iterator it = G[vs].begin(); it != G[vs].end(); it ++)
            if (d[it->x] > d[vs]+it->c && it->x != first)
            {
                d[it->x] = d[vs]+it->c;
                decrease(it->x);
            }
    }
}
int main()
{

    citire();
    first=1;
    build_heap();
    dijkstra();
    freopen(fout,"w",stdout);
    for (int i=1;i<=n;i++)
        if (i!=first)
            printf("%d ",d[i]==inf ? 0 : d[i]);
    fclose(stdout);
	return 0;
}