P1011

#include <bits/stdc++.h>

typedef long long i64;
typedef std::pair<i64, int> PLI;
const int N = 200010, M = 400010;
const i64 INF = 0x3f3f3f3f3f3f3f3f;
int n, m, s;
int head[N], nxt[M << 1], to[M << 1], wt[M << 1], idx;
i64 dis[N];
bool rem[N];
std::priority_queue<PLI, std::vector<PLI >, std::greater<PLI > > q;

void add(int u, int v, int w) {
    nxt[idx] = head[u];
    to[idx] = v;
    wt[idx] = w;
    head[u] = idx;
    ++ idx;
    return;
}
void dijkstra(void) {

    for (int i = 1; i <= n; ++ i) {
        dis[i] = INF;
        rem[i] = false;
    }
    dis[s] = 0;
    q.push(std::make_pair(dis[s], s));

    while (!q.empty()) {
        int t = q.top().second;
        q.pop();
        if (rem[t]) {
            continue;
        }
        for (int i = head[t]; i != -1; i = nxt[i]) {
            int e = to[i], w = wt[i];
            if (!rem[e] && dis[e] > dis[t] + w) {
                dis[e] = dis[t] + w;
                q.push(std::make_pair(dis[e], e));
            }
        }
    }
    return;
}

int main(void) {
    memset(head, -1, sizeof(head));
    int inpu, inpv, inpw;

    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; ++ i) {
        scanf("%d%d%d", &inpu, &inpv, &inpw);
        add(inpu, inpv, inpw);
        add(inpv, inpu, inpw);
    }
    dijkstra();
    for (int i = 1; i <= n; ++ i) {
        printf("%lld ", dis[i]);
    }

    return 0;
}