spfa

#include <stdio.h>
#include <queue>
using namespace std;
#define inf 2147483647

const int maxn = 10010, maxm = 500050;
int n, m, s;

struct edge {
    int to, weight, next;
};
edge edges[maxm];
int head[maxn], edge_cnt;

void add(int x, int y, int w) {
    edges[++edge_cnt].next = head[x];
    edges[edge_cnt].to = y;
    edges[edge_cnt].weight = w;
    head[x] = edge_cnt;
}

long long dist[maxn];
int inque[maxn];

void spfa() {
    for (int i = 1; i <= n; ++i) dist[i] = inf;
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    inque[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inque[u] = 0;
        for (int i = head[u]; i != 0; i = edges[i].next) {
            int v = edges[i].to, w = edges[i].weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inque[v]) {
                    q.push(v);
                    inque[v] = 1;
                }
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 1; i <= m; ++i) {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        add(x, y, w);
    }
    spfa();
    for (int i = 1; i <= n; ++i) printf("%lld ", dist[i]);
    return 0;
}