#include <bits/stdc++.h>

using namespace std;
const int N = 5e5 + 10;
struct Edge {
    int to, w, next;
} edge[N];
int head[N], cnt;

inline int read() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
    int res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

void add_edge(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = ++cnt;
}

int d[N], vis[N], n, m, s;
priority_queue<pair<int, int>> q;


void Dijkstra() {
    for (int i = 1; i <= n; ++i) d[i] = 2147483647;
    d[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; ~i; i = edge[i].next) {
            int y = edge[i].to;
            if (d[y] > d[x] + edge[i].w) {
                d[y] = d[x] + edge[i].w;
                q.push(make_pair(-d[y], y));
            }
        }
    }
}

int main() {
    memset(head, -1, sizeof head);
    n = read(), m = read(), s = read();
    while (m--) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    Dijkstra();
    for (int i = 1; i <= n; ++i) printf("%d ",d[i]);
    return 0;
}

输出偏大