#include <stdio.h>
#include <stdbool.h>

#define maxn 100010
#define maxm 200010
#define inf 123456789

typedef struct Edge{
    int v;
    int w;
    int next;
} Edge[maxm];
Edge edge;

bool check[maxn];
int Head[maxn], Heap[maxn], dis[maxn];
int cnt_of_list, cnt_of_heap;
int n, m, s;

void add(int u, int v, int w);
void HeapAdjust();
void PercDown(int i);
void DeleteMin();
void HeapInsert(int i);

int main()
{
    int u, v, w;
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[s] = 0;
    dis[0] = -1;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    Heap[++cnt_of_heap] = s;
    while (cnt_of_heap)
    {
        u = Heap[1];
        check[u] = 1;
        DeleteMin();
        for (int i = Head[u]; i; i = edge[i].next)
        {
            if (check[edge[i].v] == 0)
            {
                v = edge[i].v;
                w = edge[i].w;
                if (dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    HeapInsert(v);
                }
            }
        }
        HeapAdjust();
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);

    return 0;
}

void add(int u, int v, int w)
{
    edge[++cnt_of_list].v = v;
    edge[cnt_of_list].w = w;
    edge[cnt_of_list].next = Head[u];
    Head[u] = cnt_of_list;
}

void HeapAdjust()
{
    for (int i = cnt_of_heap / 2; i >= 1; i--)
        PercDown(i);
}

void PercDown(int i)
{
    int Child, Tmp;
    Tmp = Heap[i];
    while (i * 2 <= cnt_of_heap)
    {
        Child = i * 2;
        if (Child != cnt_of_heap && dis[Heap[Child]] > dis[Heap[Child + 1]])
            Child++;
        if (dis[Heap[Child]] < dis[Tmp])
        {
            Heap[i] = Heap[Child];
            i = Child;
        }
        else
            break;
    }
    Heap[i] = Tmp;
}

void DeleteMin()
{
    Heap[1] = Heap[cnt_of_heap--];
    PercDown(1);
}

void HeapInsert(int i)
{
    int Tmp = dis[i];
    int j;
    for (j = ++cnt_of_heap; j >= 1; j /= 2)
    {
        if (dis[Heap[j / 2]] > Tmp)
            Heap[j] = Heap[j / 2];
        else
            break;
    }
    Heap[j] = i;
}