最短路一：Dijkstra

// ✗ 错误版本①：把第 30 章那份 BFS 原样搬来，只把 `+1` 改成 `+w`
//
// ★ 这一份是**整章的引子**，也是第 31 章章末那句预告的正主：
//
//     第 30 章的 BFS 已经能求最短路了 —— 但那是「每条边都一样长」的情况。
//     边一带上权，**一圈一圈往外扩就不成立了。**
//
// 它和第 30 章那份 BFS 的差别只有一个加号后面的东西：
//
//     第 30 章：dist[v] = dist[u] + 1;   // 边数
//     这里：    dist[v] = dist[u] + w;   // 边长
//
// 其余一字未改：普通队列、**入队时打 vis、每个点只入队一次**。
// 而毛病就出在那句「只入队一次」上 —— 它等于宣布：
//   **谁先被碰到，谁的距离就定死。** BFS 里「先被碰到」= 边数最少，
//   可这道题要的是「边长之和最小」，两者根本不是一回事。
//
// 正文那张默认图就是照着这一点造的：
//   起点 5 到 1 号有两条路 —— 一条边直达（长 9），或者绕四条短边（2+3+1+2 = 8）。
//   BFS 一眼看到那条直达的边，就把 dist[1] 定成了 9。**走三条短边比一条长边近**，
//   这句话在这张图上是一个具体的数字：8 和 9。
//
// ⚠ 而且它在「每条边都一样长」的数据上是**完全正确**的（那时它就是第 30 章的 BFS）。
//   所以生成器要是顺手把边权全写成 1，这个 bug 会 300 轮一次都抓不到 ——
//   正文第 11 步那张表的第一行就是这么来的。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    queue<int> q;
    dist[s] = 0;
    vis[s] = 1;                                   // ✗ 第 30 章的写法：入队时就打 vis
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [v, w] : g[u]) {
            if (vis[v]) continue;                 // ✗ 「来过就不再看」—— 距离就此定死
            vis[v] = 1;
            dist[v] = dist[u] + w;                // ✗ 只把 +1 换成了 +w，别的什么都没想
            q.push(v);
        }
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// 标准答案 —— Floyd：不「一个个确定」，而是「允许中转的点越来越多」
//
// 输入：第一行 n m s（n 个点、m 条边、起点 s）
//       接下来 m 行 `u v w`，表示一条 u → v 的**有向**边，长度 w（1 ≤ w ≤ 100）
//       ⚠ 可能有重边，也可能有自环，⚠ 也可能有从 s 走不到的点
// 输出：一行 n 个数，第 i 个是「s 到 i 的最短距离」；走不到的输出 -1（s 到自己是 0）
//
// ★ 为什么标准答案挑 Floyd：它和 Dijkstra 的想法**完全不一样**。
//   Dijkstra 是「每次挑一个点，把它的距离定死」—— 一个贪心；
//   Floyd 是「d[i][j] 只允许拿前 k 个点当中转站，k 从 0 涨到 n」—— 一个 DP。
//   一个贪心、一个 DP，两边不可能一起错（第 9 章那条规矩）。
//   而且下一章（第 33 章）正好要讲它，到时候会解释「为什么 k 必须在最外层」。
//   这一章先把它当黑盒用：它慢（O(n³)），但它对。
//
// ⚠ 两个和「重边 / 自环」有关的细节，两个都是坑：
//   ① 邻接矩阵存图时**必须取 min**（`e[u][v] = min(e[u][v], w)`）。
//      写成直接赋值的话，后一条重边会把前一条更短的覆盖掉。
//      正文那张默认图特意放了一条更长的重边（5 → 6 长度 6，而前面已经有一条长度 2 的），
//      就是为了让这个坑在第一组数据上就现形。
//   ② 自环（u == v）可以直接扔掉：边长是正的，绕自己一圈只会更远。
//      而 e[i][i] 一开始就该是 0。
//
// ⚠ INF 取 0x3f3f3f3f（约 10.6 亿）而不是 INT_MAX，理由就在下面这一行：
//      d[i][k] + d[k][j]
//   两个 INF 相加 = 21.2 亿，**还没溢出 int**（上限 21.47 亿）。
//   换成 INT_MAX 的话这一句当场变成负数，「走不到的点」会被刷出一个负距离，
//   而且顺着边传染出去。0x3f3f3f3f 这个惯用法就是为了这一句而存在的。
//
// ⚠ 尽管如此，三重循环里还是加了「两头都得走得到才松弛」的守卫。为什么：
//   ★ 正文第 9 步要拿这份代码去当**负权图**的标准答案（那是本章唯一能验负权的东西）。
//   一旦有负权边，`INF + (-7)` 就比 INF 小，Floyd 会把「走不到」误当成一条 10.6 亿长的路，
//   再顺着它接下去。**这个守卫不是为正权数据加的，是为第 9 步加的。**
//   （Floyd 在有负权、但没有负环的图上仍然完全正确 —— 这也是第 33 章的内容。）

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<int>> d(n + 1, vector<int>(n + 1, INF));
    for (int i = 1; i <= n; i++) d[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u == v) continue;                     // 自环：边长为正，绕一圈只会更远
        d[u][v] = min(d[u][v], w);                // ★ 重边取 min，不能直接赋值
    }

    // ★ k 在最外层：「允许拿 1..k 当中转站」是这个 DP 的阶段。第 33 章会讲透为什么。
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++) {
            if (d[i][k] >= INF) continue;         // ⚠ 见下面那段注释：这是留给负权那一节的
            for (int j = 1; j <= n; j++)
                if (d[k][j] < INF) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }

    for (int i = 1; i <= n; i++)
        cout << (d[s][i] >= INF ? -1 : d[s][i]) << " \n"[i == n];
    return 0;
}

// ★ 这一章的关键一步，最直白的样子 —— 朴素 O(n²) Dijkstra
//
// 和 brute.cpp 解同一道题，答案必须一模一样。
//
// ★ 一句话：**每次取「当前最近的、还没定下来的点」，它的距离当场就定死了。**
//
//   为什么这个贪心是对的（反证法，三句话）：
//     设 u 是此刻 dist 最小的未确定点。假如真有一条更短的 s → u 的路，
//     那条路总要在某个地方**第一次离开「已确定的那堆点」**，设它踏出来的第一个未确定点是 x。
//     于是：那条路的长度 ≥ 走到 x 的长度 ≥ dist[x] ≥ dist[u]（最后一步因为 u 是当前最小）。
//     ——「更短」不成立，矛盾。
//
//   ⚠ 请盯住中间那个「≥」：**从 x 走到 u 的那一段长度 ≥ 0**，这一步用掉了
//     「边长非负」这个条件，而且**只用在这一处**。
//     所以负权边一出现，这个证明当场就断在这里 —— 反例也正好长在这里
//     （第 20 章那句「交换论证断在哪一步，反例就长在哪里」的第三次登场）。
//     正文第 9 步用一张 3 个点的图把它演示出来。
//
// 复杂度：外层挑 n 次，每次扫 n 个点找最小 → O(n²)；再加上每条边松弛一次 O(m)。
//         总共 O(n² + m)。
//         ★ 注意它对 m 完全不敏感 —— 边再多，那个 n² 也一分不多、一分不少。
//
// ⚠ 教科书上常有一句「稠密图就用朴素 O(n²)，稀疏图才用堆优化」。
//   ★ **这一章没能把它实测出来。** 我拧到 m ≈ n²（3000 个点、900 万条边）时，
//     两者仍然是 0.82 秒 vs 0.80 秒，堆优化**还是没输**。
//   原因在 count.cpp 数出来的那个数字上：那 900 万条边只带来 **19847 次入堆** ——
//   堆优化真正的代价不是「m log n」，而是「**成功松弛的次数** × log n」，
//   而随机图上绝大多数边根本刷不动任何人。
//   （第 29 章那条「口诀要拿实测复核」的第二次。正文第 7 步把这笔账摊开了。）

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);      // g[u] = {(v, w), …}
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});                   // 有向图只存一遍；重边、自环都原样留着
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    dist[s] = 0;

    for (int step = 0; step < n; step++) {
        // ★ 第一步：在**还没定下来的点**里挑距离最小的那个
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;

        // 剩下的点全是 INF —— 从 s 根本走不到它们，可以收工了
        if (u == -1 || dist[u] == INF) break;

        // ★ 第二步：它的距离从此定死，不会再变
        vis[u] = 1;

        // 第三步：拿它去「松弛」邻居 —— 经过 u 到 v 会不会更近？
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// 堆优化 Dijkstra —— ★ 把第 31 章那个小根堆**原样搬过来**就是它
//
// 和 naive.cpp 是同一个算法、同一个贪心，只换了一件事：
//   「在还没定下来的点里找距离最小的那个」这件事，
//   naive.cpp 是每次**扫一遍 n 个点**（O(n)），这里交给**小根堆**（O(log n)）。
//
// ★ 第 31 章章末那句预告，就在下面这一行兑现：
//
//     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> q;
//
//   第 31 章的拓扑排序里写的是 priority_queue<int, vector<int>, greater<int>>。
//   **容器一个字没变，变的是往里放什么：**
//
//     第 31 章：堆里放**编号**       → 每次取出「编号最小」的点
//     这一章：  堆里放 **(距离, 编号)** → 每次取出「距离最小」的点
//
//   pair 的比较是先比第一维，所以把距离放在前面，堆就按距离排。
//   ⚠ 只搬容器、忘了改放进去的东西，就是 wrongHeapId.cpp 那个错误版本 ——
//     它每次取的还是「编号最小」，于是编号小的点被过早定死。
//
// ★ 关于那句 `if (d > dist[u]) continue;`（「懒删除」）：
//   一个点的距离在被确定之前可能被松弛好几次，每次都往堆里塞一个新的 (距离, 编号)。
//   我们不去堆里把旧的删掉（标准堆做不到），而是等它出来的时候看一眼：
//   **它带的距离比现在记录的还大，说明它是过期的，直接扔掉。**
//   这一句同时也充当了 naive.cpp 里 vis[] 的角色 —— 一个点真正被处理只会有一次。
//
// 复杂度：每条边最多往堆里塞一次 → 堆里最多 O(m) 个元素 → O(m log m)，通常写作 O(m log n)。
//   ⚠ 但 `m log n` 是个**很松的上界**：一条边只有在「真的把某个点刷小了」的时候才入堆。
//     实测（正文第 7 步）：3000 个点、900 万条边的图上，入堆只发生了 **19847** 次 ——
//     不到边数的千分之三。所以「稠密图上堆优化会输给 O(n²)」这句常见的话，
//     在随机数据上**我没能复现出来**（0.80 秒 vs 朴素的 0.82 秒）。
//     第 29 章那句「口诀要拿实测复核，别默认它到处成立」在这一章又应验了一次。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;                       // (距离, 点的编号) —— ★ 距离必须在前

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<PII>> g(n + 1);                 // g[u] = {(v, w), …}
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> q;   // ★ 第 31 章那个小根堆，原样搬来
    dist[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;                // ★ 过期的那一份，扔掉（它同时充当 vis）
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) {
                dist[v] = d + w;
                q.push({dist[v], v});             // 距离变小了才重新入堆
            }
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// ★ 这一章的关键一步，最直白的样子 —— 朴素 O(n²) Dijkstra
//
// 和 brute.cpp 解同一道题，答案必须一模一样。
//
// ★ 一句话：**每次取「当前最近的、还没定下来的点」，它的距离当场就定死了。**
//
//   为什么这个贪心是对的（反证法，三句话）：
//     设 u 是此刻 dist 最小的未确定点。假如真有一条更短的 s → u 的路，
//     那条路总要在某个地方**第一次离开「已确定的那堆点」**，设它踏出来的第一个未确定点是 x。
//     于是：那条路的长度 ≥ 走到 x 的长度 ≥ dist[x] ≥ dist[u]（最后一步因为 u 是当前最小）。
//     ——「更短」不成立，矛盾。
//
//   ⚠ 请盯住中间那个「≥」：**从 x 走到 u 的那一段长度 ≥ 0**，这一步用掉了
//     「边长非负」这个条件，而且**只用在这一处**。
//     所以负权边一出现，这个证明当场就断在这里 —— 反例也正好长在这里
//     （第 20 章那句「交换论证断在哪一步，反例就长在哪里」的第三次登场）。
//     正文第 9 步用一张 3 个点的图把它演示出来。
//
// 复杂度：外层挑 n 次，每次扫 n 个点找最小 → O(n²)；再加上每条边松弛一次 O(m)。
//         总共 O(n² + m)。
//         ★ 注意它对 m 完全不敏感 —— 边再多，那个 n² 也一分不多、一分不少。
//
// ⚠ 教科书上常有一句「稠密图就用朴素 O(n²)，稀疏图才用堆优化」。
//   ★ **这一章没能把它实测出来。** 我拧到 m ≈ n²（3000 个点、900 万条边）时，
//     两者仍然是 0.82 秒 vs 0.80 秒，堆优化**还是没输**。
//   原因在 count.cpp 数出来的那个数字上：那 900 万条边只带来 **19847 次入堆** ——
//   堆优化真正的代价不是「m log n」，而是「**成功松弛的次数** × log n」，
//   而随机图上绝大多数边根本刷不动任何人。
//   （第 29 章那条「口诀要拿实测复核」的第二次。正文第 7 步把这笔账摊开了。）

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);      // g[u] = {(v, w), …}
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});                   // 有向图只存一遍；重边、自环都原样留着
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    dist[s] = 0;

    for (int step = 0; step < n; step++) {
        // ★ 第一步：在**还没定下来的点**里挑距离最小的那个
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;

        // 剩下的点全是 INF —— 从 s 根本走不到它们，可以收工了
        if (u == -1 || dist[u] == INF) break;

        // ★ 第二步：它的距离从此定死，不会再变
        vis[u] = 1;

        // 第三步：拿它去「松弛」邻居 —— 经过 u 到 v 会不会更近？
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// ✗ 错误版本②：小根堆搬对了，**往里放的东西搬错了**
//
// ★ 这一份是 fast.cpp 的影子。第 31 章章末说「把那个小根堆原样搬过来就是堆优化 Dijkstra」——
//   这份代码就是把那句话**照字面**执行的结果：
//
//     第 31 章：priority_queue<int, vector<int>, greater<int>> q;   // 堆里放编号
//     这里：    priority_queue<int, vector<int>, greater<int>> q;   // ✗ 一个字都没改
//     fast.cpp：priority_queue<PII, vector<PII>, greater<PII>> q;   // ✓ 堆里放 (距离, 编号)
//
// 于是它每次取出的是「**编号**最小的点」，而不是「**距离**最小的点」——
// 而 Dijkstra 的整个正确性都押在「取出来的那个必须是距离最小的」上面。
// 编号小的点被过早地定死，它后面那一串就跟着一起错。
//
// ⚠ 它有一半是对的：松弛照做、dist 也会被后来更好的值更新
//   （正文默认图上 4 号点的距离就被事后修正过一次）。
//   但**已经出过堆的点不会再往下传播**，所以错误留在了它的下游。
//   一个「只错一部分」的版本，比全错的更难发现 —— 这正是要拿它对拍的理由。
//
// ⚠ 还有一个「顺手」会让它隐身：如果生成器造出来的图，编号顺序恰好和距离顺序一致
//   （比如起点固定 1 号、边只连编号小 → 大），它就是对的。第 27、31 章那条
//   「别让编号自己带上一层题目没给的含义」在这一章仍然有效。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    priority_queue<int, vector<int>, greater<int>> q;   // ✗ 堆里放的是**编号**
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.top();                          // ✗ 取出来的是编号最小的，不是距离最小的
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                q.push(v);
            }
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// ✗ 错误版本③：找最小值的时候，忘了排除「已经定下来的点」
//
// 和 naive.cpp 只差三个字符：
//
//     naive.cpp： if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
//     这里：      if (            u == -1 || dist[j] < dist[u] ) u = j;   // ✗ 少了 !vis[j]
//
// 后果比想象的严重得多：起点的 dist 是 0，是全场最小的，
// 所以**每一轮挑出来的都是起点**。松弛 n 遍起点的出边，图上其余部分根本没被碰过。
// 最后只有「起点的直接邻居」有距离，别的全是 -1。
//
// ★ 它错得这么彻底，是件好事 —— 对拍第 1 轮就会抓到它。
//   真正难缠的是 wrongHeapId 那种「只错一部分」的。把两种都留着，
//   是为了让学生看见「bug 的可见度」本身就有天壤之别。
//
// ⚠ 顺带说一句它为什么不会死循环：外层是 `for (step < n)` 的固定 n 轮，不是 while。
//   要是写成「一直挑到没有未确定的点为止」，这一份就会转不出来了。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    dist[s] = 0;

    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (u == -1 || dist[j] < dist[u]) u = j;        // ✗ 没排除已经定下来的点
        if (u == -1 || dist[u] == INF) break;
        vis[u] = 1;
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// ✗ 错误版本④：松弛时忘了「更近才更新」，直接赋值
//
// 和 naive.cpp 只差一个 if：
//
//     naive.cpp： if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
//     这里：                                 dist[v] = dist[u] + w;    // ✗ 无条件覆盖
//
// 「松弛」这个词本身就说明了那个 if 不能省：
//   **松弛的意思是「如果经过 u 更近，就把 v 的距离放松到这个更小的值」** ——
//   它天生是单向的，只许变小，不许变大。
//
// ⚠ 有两种数据能让它现形，正文那张默认图两种都留了（都是实测确认过的）：
//   ① **重边**：`5 → 6` 有两条，长度 2 和 6。正确的松弛第二次看一眼 6 > 2 就走了，
//      这一份直接把 6 号点的距离从 2 改成了 6 —— 而 6 号是整条链的起头，
//      于是它下游那一串全跟着变大。这也是它在默认图上错得那么惨的原因
//      （`12 16 -1 19 0 6 9`，只有起点是对的）。
//   ② **回指的边**：`2 → 4`，2 号距离 9、4 号距离 6。正确的松弛看一眼 9 + 3 = 12 > 6 就走了，
//      这一份把一个**已经算对的**距离改成了更大的值。
//
// ★ 所以这一份是给**生成器**出的两道题：数据里得有重边，也得有「从远处指回近处」的边。
//   只造「越走越远、而且没有重边」的图（这正是「顺手写个简单 DAG」的样子），它就隐身了。
//   第 29 章那条「顺手去掉自环和重边」的教训，在这一章换了个身份又出现了一次。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    dist[s] = 0;

    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) break;
        vis[u] = 1;
        for (auto [v, w] : g[u])
            dist[v] = dist[u] + w;                // ✗ 没问「是不是更近」就写了进去
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// ✗ 错误版本⑤：走不到的点，忘了输出 -1
//
// 和 naive.cpp 只差最后一行：
//
//     naive.cpp： cout << (dist[i] >= INF ? -1 : dist[i]);
//     这里：      cout << dist[i];                          // ✗ 直接把 INF 打了出去
//
// 六个错误版本里它最不「聪明」——算法本身一个字没错，错的是收尾。
// 留着它是因为它**专门用来检验生成器**，而且检验的正是这一章最容易被顺手做掉的那件事：
//
//     ★ 如果数据保证「从起点能走到所有点」，这一份就 300 轮全对。
//
//   而「保证处处可达」几乎是每个人写图生成器的条件反射 ——
//   因为一串 -1 的输出「看着不像话」。第 30 章刚刚在同一件事上栽过
//   （那一章「走不到就输出 0」的 bug 在保证连通的数据上是 0 / 300）。
//   正文第 11 步那张表里，它就是从 0 跳到非 0 的那一行。
//
// ⚠ 顺带戳破一个常见的想当然：很多人以为「不判可达就去松弛」会把 INF 传染出去
//   （`dist[邻居] = INF + w`）。用 0x3f3f3f3f 时**不会** ——
//   因为松弛的条件是 `dist[u] + w < dist[v]`，而 INF + w 比 INF **大**，这一句根本不成立。
//   我第一版就是这么写的，实测发现它和正解一模一样，只好改成现在这样。
//   （真会溢出成负数的是 INT_MAX 那种写法，那属于未定义行为，教材里不演示。）
//   **「我以为它会错」和「它真的错了」之间，隔着一次实测。**

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    dist[s] = 0;

    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) break;
        vis[u] = 1;
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }

    for (int i = 1; i <= n; i++)
        cout << dist[i] << " \n"[i == n];         // ✗ 走不到的点应该输出 -1，这里原样打了 INF
    return 0;
}

// ✗ 错误版本⑥：从 1 号点出发，而不是从题目给的 s
//
// 和 naive.cpp 只差一个字符：`dist[s] = 0` 写成了 `dist[1] = 0`。
// 算法一点毛病没有，**错的是读题**。
//
// ★ 它其实不是「bug」，是一块**试金石**（第 31 章 wrongIdentity.cpp 那件工具的第二次使用）：
//   它专门用来检查**生成器有没有把起点固定成 1 号**。
//   如果生成器顺手写了 `s = 1`（"反正题目没说不行"），这一份就 300 轮全对，
//   而你会以为自己的数据挺好。
//
//   第 30 章刚在这上面栽过一次：那一章「从 1 号出发」这个 bug 在
//   「起点永远是 1」的数据上是 0 / 300，把起点随机化之后立刻 244 / 300。
//   **同一个坑，隔了两章又来了一次** —— 所以这条要当成硬规矩：
//   **凡是题目里出现「起点 / 根 / 第一个」这种角色，就不许让它固定在 1 号。**

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF), vis(n + 1, 0);
    dist[1] = 0;                                  // ✗ 题目给的起点是 s，不是 1

    for (int step = 0; step < n; step++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) break;
        vis[u] = 1;
        for (auto [v, w] : g[u])
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// 堆优化 Dijkstra —— ★ 把第 31 章那个小根堆**原样搬过来**就是它
//
// 和 naive.cpp 是同一个算法、同一个贪心，只换了一件事：
//   「在还没定下来的点里找距离最小的那个」这件事，
//   naive.cpp 是每次**扫一遍 n 个点**（O(n)），这里交给**小根堆**（O(log n)）。
//
// ★ 第 31 章章末那句预告，就在下面这一行兑现：
//
//     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> q;
//
//   第 31 章的拓扑排序里写的是 priority_queue<int, vector<int>, greater<int>>。
//   **容器一个字没变，变的是往里放什么：**
//
//     第 31 章：堆里放**编号**       → 每次取出「编号最小」的点
//     这一章：  堆里放 **(距离, 编号)** → 每次取出「距离最小」的点
//
//   pair 的比较是先比第一维，所以把距离放在前面，堆就按距离排。
//   ⚠ 只搬容器、忘了改放进去的东西，就是 wrongHeapId.cpp 那个错误版本 ——
//     它每次取的还是「编号最小」，于是编号小的点被过早定死。
//
// ★ 关于那句 `if (d > dist[u]) continue;`（「懒删除」）：
//   一个点的距离在被确定之前可能被松弛好几次，每次都往堆里塞一个新的 (距离, 编号)。
//   我们不去堆里把旧的删掉（标准堆做不到），而是等它出来的时候看一眼：
//   **它带的距离比现在记录的还大，说明它是过期的，直接扔掉。**
//   这一句同时也充当了 naive.cpp 里 vis[] 的角色 —— 一个点真正被处理只会有一次。
//
// 复杂度：每条边最多往堆里塞一次 → 堆里最多 O(m) 个元素 → O(m log m)，通常写作 O(m log n)。
//   ⚠ 但 `m log n` 是个**很松的上界**：一条边只有在「真的把某个点刷小了」的时候才入堆。
//     实测（正文第 7 步）：3000 个点、900 万条边的图上，入堆只发生了 **19847** 次 ——
//     不到边数的千分之三。所以「稠密图上堆优化会输给 O(n²)」这句常见的话，
//     在随机数据上**我没能复现出来**（0.80 秒 vs 朴素的 0.82 秒）。
//     第 29 章那句「口诀要拿实测复核，别默认它到处成立」在这一章又应验了一次。

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;                       // (距离, 点的编号) —— ★ 距离必须在前

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<vector<PII>> g(n + 1);                 // g[u] = {(v, w), …}
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    vector<int> dist(n + 1, INF);
    priority_queue<PII, vector<PII>, greater<PII>> q;   // ★ 第 31 章那个小根堆，原样搬来
    dist[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) continue;                // ★ 过期的那一份，扔掉（它同时充当 vis）
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) {
                dist[v] = d + w;
                q.push({dist[v], v});             // 距离变小了才重新入堆
            }
    }

    for (int i = 1; i <= n; i++)
        cout << (dist[i] >= INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}