#include <stdio.h>

#define ls (now << 1)
#define rs (now << 1 | 1)
#define fa (now >> 1)

const int inf = 2147483647;

int n, m, s, tot, tal;
int heap[2000010], heap_id[2000010];
int to[2000010], hed[2000010], net[2000010], val[2000010], dis[2000010];

void Add_edge(int u, int v, int w) {
    val[++tal] = w, to[tal] = v, net[tal] = hed[u];
    hed[u] = tal;

}

void ins(int x, int point) {
    heap[++tot] = x, heap_id[tot] = point;
    int now = tot;
    while(heap[fa] > heap[now] && now != 1) {
        int mm = heap[fa], nn = heap_id[fa];
        heap[fa] = heap[now], heap_id[fa] = heap_id[now];
        heap[now] = mm, heap_id[now] = nn;
        now >>= 1;
    }
}

void delete() {
    int mm = heap[1], nn = heap_id[1];
    heap[1] = heap[tot], heap[tot] = mm;
    heap_id[1] = heap_id[tot], heap_id[tot] = nn;
    heap[tot] = inf, heap_id[tot--] = 0;
    int now = 1;
    while(heap[now] > heap[ls] || heap[now] > heap[rs]) {
        if(heap[ls] < heap[rs]) {
            int mm = heap[ls], nn = heap_id[ls];
            heap[ls] = heap[now], heap[now] = mm;
            heap_id[ls] = heap_id[now], heap_id[now] = nn;
            now = ls;
        }
        else {
            int mm = heap[rs], nn = heap_id[rs];
            heap[rs] = heap[now], heap[now] = mm;
            heap_id[rs] = heap_id[now], heap_id[now] = nn;
            now = rs;
        }
    }
}

void Dijkstra() {
    ins(0, s);
    while(tot != 0) {
        int now = heap_id[1], dss = heap[1];
        delete();
        if(dis[now] != dss)
            continue;
        for(int i = hed[now]; i; i = net[i]) {
            int v = to[i], vv = val[i];
            if(dis[v] > dss + vv) {
                dis[v] = dss + vv;
                ins(dis[v], v);
            }
        }
    }
    for(int i = 1; i <= n; ++i)
        printf("%d ", dis[i]);
}

int main() {
    scanf("%d %d %d", &n, &m, &s);
    for(int i = 1; i <= (n << 1); ++i)
        heap[i] = inf;
    for(int i = 1; i <= n; ++i)
        dis[i] = inf;
    dis[s] = 0;
    for(int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        Add_edge(u, v, w);
    }
    Dijkstra();
    return 0;
}