#include <bits/stdc++.h> using namespace std; using ll = long long; using p = pair<ll, int>; const int maxn = 2e5 + 10; int cnt = -1; int head[maxn]; ll dis[maxn]; bool visted[maxn]; struct Edge{ int to, next, wt; }edges[maxn]; void add(int u, int v, int w) { edges[++cnt].to = v; edges[cnt].wt = w; edges[cnt].next = head[u]; head[u] = cnt; } void dijkstra(int src) { priority_queue<p, vector<p>, greater<p> > que; memset(visted, false, sizeof visted); memset(dis, 0x3f, sizeof dis); dis[src] = 0; que.push({0, src}); while (!que.empty()) { int u = que.top().second; que.pop(); if (visted[u]) continue; //出队时才能判断是不是最短路 visted[u] = true; for (int i = head[u];~i;i = edges[i].next) { int v = edges[i].to, w = edges[i].wt; if (!visted[v] and dis[v] > dis[u] + w) { dis[v] = dis[u] + w; que.push({dis[v], v}); } } } } int main() { #ifndef ONLINE_JUDGE freopen("D:/VS CODE/C++/in.txt", "r", stdin); freopen("D:/VS CODE/C++/out.txt", "w", stdout); #endif memset(head, -1, sizeof head); int n, m, s; cin >> n >> m >> s; for (int i = 0;i < m;++i) { int u, v, w; scanf("%d %d %d", &u, &v, &w); add(u, v, w); } dijkstra(s); for (int i = 1; i <= n; ++i) { cout << dis[i] << " \n"[i == n]; } fclose(stdin); fclose(stdout); return 0; }