64pts求调，玄关

#include <iostream>
#include <queue>
#include <cstdio>
#define int long long

using namespace std;

const int N = 1e5 + 1, Inf = 1e18;

int n, m, k;
struct edge {
    int v, w, next;
} e[2 * N];
int head[N];
int cnt;
struct node {
    int ans, id;
    bool operator <(const node &x) const {
        return x.ans > ans;
    }
};
priority_queue<node> q;
int dis[N];
bool vis[N];

void add(int u, int v, int w) {
    e[++ cnt].v = v, e[cnt].w = w, e[cnt].next = head[u], head[u] = cnt;
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 1; i <= n; i ++ )
        dis[i] = Inf;
    dis[k] = 0;
    for (int i = 1; i <= m; i ++ ) {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        add(u, v, w);
    }
    int u;
    q.push(node {0, k});
    while (!q.empty()) {
        u = q.top().id;
        q.pop();
        if (vis[u])
            continue;
        vis[k] = true;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (!vis[v])
                    q.push(node {dis[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i ++ )
        printf("%d ", dis[i]);
    return 0;
}