#include <stdio.h>

#define Nmax 100

struct Nod { int a,c; Nod *x;};

Nod *l[Nmax];
int n,m,sursa;
char v[Nmax];
int dist[Nmax];

void citire()
{
    freopen("graf.in","r",stdin);
    freopen("graf.out","w",stdout);
    
    scanf("%d%d%d", &n,&m,&sursa);
    
    for (int i=1;i<=m;++i)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        Nod *q = new Nod;
        q->a = b;
        q->c = c;
        q->x = l[a];
        l[a] = q;    
    }    
}

void afis()
{
    for (int i=1;i<=n;++i)
    printf("%d ", dist[i]);    
    printf("\n");
}

#define Inf 123456789

void relaxeaza(int nod)
{
    v[nod] = 1;    
    for (Nod *it=l[nod];it;it=it->x)
    if (dist[nod]+it->c < dist[it->a])
    dist[it->a] = dist[nod] + it->c;
}

void dijkstra()
{
    for (int i=0;i<=n;++i)
    dist[i] = Inf;
    dist[sursa] = 0;
    for (int pas=1;pas<=n;++pas)
    {
        int min = 0;
        for (int i=1;i<=n;++i)
        if (dist[i] < dist[min] && v[i] == 0) min = i;
        relaxeaza(min);    
    }
}
int main()
{    
    citire();
    
    dijkstra();
    
    afis();
    
    return 0;
}