最短路二：Floyd、Bellman-Ford、SPFA 与负环

// 标准答案 —— Floyd：把「允许拿哪些点当中转站」当成 DP 的阶段
//
// 输入：第一行 n m s
//       接下来 m 行 `u v w`，表示一条 u → v 的**有向**边，长 w（⚠ **w 可以是负数**，|w| ≤ 100）
//       ⚠ 可能有重边、自环，也可能有从 s 走不到的点
// 输出：如果从 s 出发**能走到**某个负环，输出一行 `NEGATIVE`（最短路不存在）；
//       否则输出一行 n 个数：第 i 个是 s 到 i 的最短距离，**走不到的输出 `x`**。
//
// ⚠ 为什么走不到用 `x` 而不是第 32 章那个 `-1`：这一章的距离**可以是负数**，
//   -1 是一个完全合法的距离。**答案的记号和数据的取值范围是一对，改了一边就得对一遍另一边。**
//
// ★ 这一章的关键一步，就在下面那三重循环的**顺序**上：
//
//       for (k) for (i) for (j)  d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
//                ↑ k 必须在最外层
//
//   原因不是「大家都这么写」，而是它本来有三维：
//
//       f[k][i][j] = 只允许拿 1..k 当中转站时，i 到 j 的最短距离
//       f[k][i][j] = min( f[k-1][i][j],  f[k-1][i][k] + f[k-1][k][j] )
//                          ↑ 不用 k        ↑ 用 k（而且只用一次，用两次没意义）
//
//   **k 是阶段，i 和 j 只是表格里的格子。** 阶段必须在最外层 ——
//   这和第 21 章那句「依赖谁，就先填谁」是同一句话（这是它第七次登场）。
//   而「转移右边用的必须是 k−1 那一层」和第 23 章 01 背包那句
//   「转移右边的第一维必须是 i−1」是**同一个形状**，只不过那里滚动掉的是物品、这里是中转站。
//   ⚠ 第一维能滚掉（写成二维 d[i][j]）是因为 f[k][i][k] == f[k-1][i][k]：
//     多一个 k 可以中转，对「到 k 的距离」毫无帮助（绕经自己只会更远，除非有负环）。
//   把 k 挪到里层就全乱了 —— 那就是 wrongK.cpp，正文第 5 步专门讲。
//
// ★ 负环怎么判：跑完之后 `d[k][k] < 0` ⇔ k 在某个负环上。
//   ⚠ 但题目问的是「**从 s 能走到的**负环」，所以还要加一句 `d[s][k] < INF`。
//     Floyd 看的是全图，它天生不知道 s 是谁 —— 这个过滤是**必须自己补上**的。
//     （对照 bell.cpp / spfa.cpp：那两份从 s 出发算，这个过滤是白送的。
//      正文第 8 步那个 wrongGlobalNeg.cpp 就是漏了这一句。）
//
// 复杂度 O(n³)。这一章 n 很小，它当标准答案正合适：
// 它和 Bellman-Ford「一轮一轮松弛所有边」的想法完全不同，一个是 DP、一个是迭代逼近。

#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;
        // ⚠ 自环这一次**不能扔**：负的自环本身就是一个最短的负环
        d[u][v] = min(d[u][v], w);                // 重边取 min（第 32 章那条）
    }

    // ★ k 在最外层。⚠ 两头都走得到才松弛 —— 有负权时 `INF + (-7) < INF` 是成立的
    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]);
        }

    // 从 s 能走到的负环
    for (int k = 1; k <= n; k++)
        if (d[k][k] < 0 && d[s][k] < INF) { cout << "NEGATIVE\n"; return 0; }

    for (int i = 1; i <= n; i++) {
        if (d[s][i] >= INF) cout << "x";
        else cout << d[s][i];
        cout << " \n"[i == n];
    }
    return 0;
}

// 标准答案 —— Floyd：把「允许拿哪些点当中转站」当成 DP 的阶段
//
// 输入：第一行 n m s
//       接下来 m 行 `u v w`，表示一条 u → v 的**有向**边，长 w（⚠ **w 可以是负数**，|w| ≤ 100）
//       ⚠ 可能有重边、自环，也可能有从 s 走不到的点
// 输出：如果从 s 出发**能走到**某个负环，输出一行 `NEGATIVE`（最短路不存在）；
//       否则输出一行 n 个数：第 i 个是 s 到 i 的最短距离，**走不到的输出 `x`**。
//
// ⚠ 为什么走不到用 `x` 而不是第 32 章那个 `-1`：这一章的距离**可以是负数**，
//   -1 是一个完全合法的距离。**答案的记号和数据的取值范围是一对，改了一边就得对一遍另一边。**
//
// ★ 这一章的关键一步，就在下面那三重循环的**顺序**上：
//
//       for (k) for (i) for (j)  d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
//                ↑ k 必须在最外层
//
//   原因不是「大家都这么写」，而是它本来有三维：
//
//       f[k][i][j] = 只允许拿 1..k 当中转站时，i 到 j 的最短距离
//       f[k][i][j] = min( f[k-1][i][j],  f[k-1][i][k] + f[k-1][k][j] )
//                          ↑ 不用 k        ↑ 用 k（而且只用一次，用两次没意义）
//
//   **k 是阶段，i 和 j 只是表格里的格子。** 阶段必须在最外层 ——
//   这和第 21 章那句「依赖谁，就先填谁」是同一句话（这是它第七次登场）。
//   而「转移右边用的必须是 k−1 那一层」和第 23 章 01 背包那句
//   「转移右边的第一维必须是 i−1」是**同一个形状**，只不过那里滚动掉的是物品、这里是中转站。
//   ⚠ 第一维能滚掉（写成二维 d[i][j]）是因为 f[k][i][k] == f[k-1][i][k]：
//     多一个 k 可以中转，对「到 k 的距离」毫无帮助（绕经自己只会更远，除非有负环）。
//   把 k 挪到里层就全乱了 —— 那就是 wrongK.cpp，正文第 5 步专门讲。
//
// ★ 负环怎么判：跑完之后 `d[k][k] < 0` ⇔ k 在某个负环上。
//   ⚠ 但题目问的是「**从 s 能走到的**负环」，所以还要加一句 `d[s][k] < INF`。
//     Floyd 看的是全图，它天生不知道 s 是谁 —— 这个过滤是**必须自己补上**的。
//     （对照 bell.cpp / spfa.cpp：那两份从 s 出发算，这个过滤是白送的。
//      正文第 8 步那个 wrongGlobalNeg.cpp 就是漏了这一句。）
//
// 复杂度 O(n³)。这一章 n 很小，它当标准答案正合适：
// 它和 Bellman-Ford「一轮一轮松弛所有边」的想法完全不同，一个是 DP、一个是迭代逼近。

#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;
        // ⚠ 自环这一次**不能扔**：负的自环本身就是一个最短的负环
        d[u][v] = min(d[u][v], w);                // 重边取 min（第 32 章那条）
    }

    // ★ k 在最外层。⚠ 两头都走得到才松弛 —— 有负权时 `INF + (-7) < INF` 是成立的
    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]);
        }

    // 从 s 能走到的负环
    for (int k = 1; k <= n; k++)
        if (d[k][k] < 0 && d[s][k] < INF) { cout << "NEGATIVE\n"; return 0; }

    for (int i = 1; i <= n; i++) {
        if (d[s][i] >= INF) cout << "x";
        else cout << d[s][i];
        cout << " \n"[i == n];
    }
    return 0;
}

// ✗ 错误版本① —— ★ 本章的主角：Floyd 的 k 没放在最外层
//
// 和 brute.cpp 只差**三行的顺序**：
//
//     brute.cpp： for (k) for (i) for (j)      // ✓ 阶段在最外层
//     这里：      for (i) for (j) for (k)      // ✗ 阶段跑到最里层去了
//
// 这是整个图论里被写错次数最多的一处，而且**它经常给出正确答案** ——
// 这才是它可怕的地方（正文第 6 步那张表：300 轮里它只错 XX 轮，其余全对）。
//
// ★ 为什么错：Floyd 本来是三维的 DP
//
//     f[k][i][j] = 只允许拿 1..k 当中转站时，i 到 j 的最短距离
//     f[k][i][j] = min( f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j] )
//
//   **k 是阶段**（第 21 章那句「依赖谁就先填谁」），i、j 只是表格里的格子。
//   把 k 放到最里层，等于在「还没算完 k−1 那一层」的时候就去用它 ——
//   `d[i][j]` 拿到的是一堆半成品。
//
//   具体到这一份：外层固定 i、j 之后，内层把 k 从 1 扫到 n，
//   期间用到的 `d[i][k]` 和 `d[k][j]` 里，很多格子**这一轮压根还没被更新过**。
//   于是它只找得到「一次中转」附近的路，两次以上的中转经常漏掉。
//
// ⚠ 它错得非常「安静」：不崩溃、不报错、大部分数据上答案还是对的。
//   只有当最短路**必须拐好几个弯**、而且那些弯的编号顺序不巧时才会现形。
//   ★ 所以这一份是给**生成器**出的一道题：数据里得有「绕好几个中转点才最短」的路。
//   （正文第 9 步那张表里，让它现形的那一处改动是「掺一条长链进去」。）

#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;
        d[u][v] = min(d[u][v], w);
    }

    // ✗ 阶段 k 被放到了最里层
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                if (d[i][k] < INF && d[k][j] < INF)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    for (int k = 1; k <= n; k++)
        if (d[k][k] < 0 && d[s][k] < INF) { cout << "NEGATIVE\n"; return 0; }

    for (int i = 1; i <= n; i++) {
        if (d[s][i] >= INF) cout << "x";
        else cout << d[s][i];
        cout << " \n"[i == n];
    }
    return 0;
}

// ★ Bellman-Ford —— 负权的正经办法，也是这一章第二个关键一步
//
// 和 brute.cpp（Floyd）解同一道题，答案必须一模一样。
//
// ★ 一句话：**把所有边挨个松弛一遍，叫一轮；跑 n−1 轮就够了。**
//
//   为什么是 n−1，而且一轮不多一轮不少 —— 关键在这个不变量：
//
//       跑完第 i 轮之后，dist[v] ≤「从 s 出发、**最多走 i 条边**能到 v 的最短长度」
//
//   （归纳一行就完了：第 i 轮松弛边 (u,v) 时，dist[u] 已经不差于「最多 i−1 条边」的答案。）
//
//   而**没有负环时，最短路一定是一条简单路径** —— 它最多经过 n 个点、也就是 n−1 条边。
//   所以 n−1 轮之后一定收敛。★ 「n−1」不是背下来的，是「简单路径最多 n−1 条边」这句话。
//
// ★ 判负环是白送的（第 31 章「判环白送」的第二次）：
//
//       跑完 n−1 轮之后，**再跑一轮**。要是还有边能松弛成功 —— 有负环。
//
//   为什么：能松弛成功说明存在一条「用了 n 条边还更短」的走法，
//   n 条边的走法必然重复经过某个点，也就是绕了一个环，而绕它让距离变小 → 那是负环。
//
//   ⚠ 而且这份代码天生只报告「**从 s 能走到的**负环」：
//     dist 是从 s 初始化的，走不到的点永远是 INF，`if (dist[u] == INF) continue;` 会把它挡住。
//     ★ 对照 brute.cpp：Floyd 看的是全图，那个过滤必须自己补一句 `d[s][k] < INF`。
//     **同一个题面，两种算法一个天生满足、一个必须手动补** —— 这种地方最容易写出不一致。
//
// ⚠ `if (dist[u] == INF) continue;` 这一句在**负权图上是必须的**，不是保险：
//   `INF + (-7)` 比 INF 小，不挡住的话，走不到的点会被刷出一个「比 INF 小一点」的距离，
//   而且顺着边传染。第 32 章那个「以为会传染、实测不会」的坑，在这一章**真的会**发生 ——
//   因为那时边权非负。**同一句代码危不危险，取决于数据的取值范围。**
//
// 复杂度 O(nm)：n 轮，每轮扫 m 条边。比 Floyd 的 O(n³) 好在稀疏图上。

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

const int INF = 0x3f3f3f3f;

struct E { int u, v, w; };

int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<E> es(m);
    for (auto& e : es) cin >> e.u >> e.v >> e.w;

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

    // ★ n−1 轮就够了：没有负环时，最短路是简单路径，最多 n−1 条边
    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (auto [u, v, w] : es) {
            if (dist[u] == INF) continue;         // ⚠ 负权下这一句是必须的，见上面
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
        }
        if (!changed) break;                      // 提前收敛了就不用跑满（不影响正确性）
    }

    // ★ 第 n 轮：还能松弛成功 ⇔ 从 s 能走到一个负环
    for (auto [u, v, w] : es) {
        if (dist[u] == INF) continue;
        if (dist[u] + w < dist[v]) { cout << "NEGATIVE\n"; return 0; }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] >= INF) cout << "x";
        else cout << dist[i];
        cout << " \n"[i == n];
    }
    return 0;
}

// ✗ 错误版本② —— Bellman-Ford 的轮数少了一轮
//
// 和 bell.cpp 只差一个数字：
//
//     bell.cpp： for (int round = 1; round <= n - 1; round++)
//     这里：     for (int round = 1; round <= n - 2; round++)     // ✗ 少跑一轮
//
// ★ 它专门用来验「n−1 这个数字到底是不是随便写的」。
//   n−1 的来历是：**没有负环时最短路一定是简单路径，最多经过 n 个点、n−1 条边**；
//   而「跑完第 i 轮之后 dist 不差于『最多 i 条边』的答案」。
//   少跑一轮，就是「最多 n−2 条边」—— 只要有一条最短路**正好用满 n−1 条边**，它就漏了。
//
// ⚠ 而这种路在随机图上很少见：点少边多的时候，最短路往往两三条边就走完了。
//   ★ 所以它也是给**生成器**出的题，而且要的东西和 wrongK.cpp 一样：
//   数据里得有**长链** —— 一条必须老老实实一格一格走过去的路。
//   （正文第 9 步：掺入长链之前它是 0 / 300。）
//
// ⚠ 另外那句提前收敛的 `if (!changed) break;` 也一起删了。
//   留着它的话，图小的时候往往早就收敛完了，这个 bug 会被那句 break 顺手补上 ——
//   **一个「优化」把 bug 盖住了**，那就验不出「n−1 是不是必须的」。
//   （这也是一条经验：**做错误版本时，别让无关的优化替它把窟窿补上。**）

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

const int INF = 0x3f3f3f3f;

struct E { int u, v, w; };

int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<E> es(m);
    for (auto& e : es) cin >> e.u >> e.v >> e.w;

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

    for (int round = 1; round <= n - 2; round++) {          // ✗ 应该是 n − 1
        for (auto [u, v, w] : es) {
            if (dist[u] == INF) continue;
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
        }
    }

    for (auto [u, v, w] : es) {
        if (dist[u] == INF) continue;
        if (dist[u] + w < dist[v]) { cout << "NEGATIVE\n"; return 0; }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] >= INF) cout << "x";
        else cout << dist[i];
        cout << " \n"[i == n];
    }
    return 0;
}

// 把三种算法的「工作量」数出来 —— 光看秒表说不清谁在做什么
//
// 用法：./count < 输入
//
// 数三件事：
//   · Floyd            ：三重循环跑了多少次（那就是 n³）
//   · Bellman-Ford     ：松弛**尝试**了多少次、其中**成功**了多少次
//   · SPFA             ：入队多少次、松弛尝试 / 成功多少次
//
// ★ 第二行那两个数是这一章最值钱的一组对照：
//
//     Bellman-Ford 每一轮都把 m 条边全扫一遍，可其中**绝大多数是白扫的** ——
//     一条边只有在 dist[u] 刚刚变小时才可能松弛成功。
//     **SPFA 的全部内容就是「别扫那些白扫的」**：谁变小了就把谁排队。
//
//   正文第 7 步拿这两个数把「为什么会想到 SPFA」讲成了一个可以量的事实，
//   而不是「有个优化叫 SPFA」。
//
// ⚠ 有负环时 Bellman-Ford / SPFA 会提前报 NEGATIVE 退出，那时数出来的是「到发现为止」的工作量。

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

const int INF = 0x3f3f3f3f;
struct E { int u, v, w; };

int main() {
    int n, m, s;
    if (scanf("%d %d %d", &n, &m, &s) != 3) return 0;
    vector<E> es(m);
    vector<vector<pair<int, int>>> g(n + 1);
    for (auto& e : es) {
        if (scanf("%d %d %d", &e.u, &e.v, &e.w) != 3) break;
        g[e.u].push_back({e.v, e.w});
    }

    /* ---------- Floyd ---------- */
    long long floydSteps = 0;
    // ⚠ n 一大，Floyd 的 n³ 本身就跑不动了（n = 2000 是 80 亿次）——
    //   而「跑不动」正是这一节要说的话，所以大图上直接不跑，只报公式。
    bool floydSkipped = (n > 400);
    if (!floydSkipped) {
        vector<vector<int>> d(n + 1, vector<int>(n + 1, INF));
        for (int i = 1; i <= n; i++) d[i][i] = 0;
        for (auto& e : es) d[e.u][e.v] = min(d[e.u][e.v], e.w);
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++) {
                    floydSteps++;
                    if (d[i][k] < INF && d[k][j] < INF)
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
    }

    /* ---------- Bellman-Ford ---------- */
    long long bfTry = 0, bfOk = 0;
    int bfRounds = 0;
    bool bfNeg = false;
    {
        vector<int> dist(n + 1, INF);
        dist[s] = 0;
        for (int round = 1; round <= n - 1; round++) {
            bool changed = false;
            bfRounds++;
            for (auto [u, v, w] : es) {
                if (dist[u] == INF) continue;
                bfTry++;
                if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; bfOk++; changed = true; }
            }
            if (!changed) break;
        }
        for (auto [u, v, w] : es) {
            if (dist[u] == INF) continue;
            if (dist[u] + w < dist[v]) { bfNeg = true; break; }
        }
    }

    /* ---------- SPFA ---------- */
    long long spPush = 0, spTry = 0, spOk = 0;
    bool spNeg = false;
    {
        vector<int> dist(n + 1, INF), cnt(n + 1, 0), inq(n + 1, 0);
        queue<int> q;
        dist[s] = 0; q.push(s); inq[s] = 1; spPush++;
        while (!q.empty() && !spNeg) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (auto [v, w] : g[u]) {
                spTry++;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w; spOk++;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) { spNeg = true; break; }
                    if (!inq[v]) { q.push(v); inq[v] = 1; spPush++; }
                }
            }
        }
    }

    printf("n = %d 个点，m = %d 条边，起点 s = %d\n\n", n, m, s);
    long long n3 = (long long)n * n * n;
    if (floydSkipped)
        printf("Floyd        ：n = %d 时三重循环要跑 %lld 次 —— 这一档直接没跑它\n", n, n3);
    else
        printf("Floyd        ：三重循环 %lld 次（n^3 = %lld）\n", floydSteps, n3);
    printf("Bellman-Ford ：跑了 %d 轮，松弛尝试 %lld 次，其中成功 %lld 次\n", bfRounds, bfTry, bfOk);
    printf("SPFA         ：入队 %lld 次，松弛尝试 %lld 次，其中成功 %lld 次\n", spPush, spTry, spOk);
    printf("\n");
    if (bfTry > 0)
        printf("★ Bellman-Ford 的松弛里只有 %.1f%% 是有用的（%lld / %lld）——\n"
               "  剩下那些全是白扫的边。SPFA 的全部内容就是「别扫它们」：\n"
               "  它只尝试了 %lld 次，是 Bellman-Ford 的 %.2f 倍。\n",
               100.0 * bfOk / bfTry, bfOk, bfTry, spTry, bfTry ? (double)spTry / bfTry : 0.0);
    printf("\n判负环：Bellman-Ford 说 %s，SPFA 说 %s\n",
           bfNeg ? "有" : "没有", spNeg ? "有" : "没有");
    return 0;
}

// SPFA —— Bellman-Ford 的队列优化
//
// 和 brute.cpp / bell.cpp 解同一道题，答案必须一模一样。
//
// ★ 想法只有一句：**Bellman-Ford 每轮都把所有边扫一遍，可其中绝大多数是白扫的。**
//
//   一条边 (u, v) 只有在 dist[u] **刚刚变小**的时候才可能松弛成功。
//   所以：谁的 dist 变小了，就把谁排队；从队列里取一个点出来，只松弛它的出边。
//   —— 这就是 SPFA，一个字都没多。
//
// ★★ 而这里有一件第 32 章埋好的伏笔，现在可以挑明了：
//
//     **SPFA 和第 32 章那份「在负权图上不小心答对了」的堆优化 Dijkstra，是同一件事。**
//
//   把这份代码里的 `queue` 换成「按 dist 排序的小根堆」，它逐字逐句就是那份 fast.cpp
//   （连那句 `if (d > dist[u]) continue;` 都对应这里的 inq 判重）。
//   第 32 章说「堆优化在负权图上 300 轮一次都没错」——
//   现在知道原因了：**它当时执行的根本不是 Dijkstra，而是这个算法。**
//   ⚠ 所以那句话的正确说法始终是：**不成立的是「取出来就定死」那个贪心。**
//
// ★ 判负环：给每个点记一个 cnt[v] = 「当前这条到 v 的最短路用了几条边」。
//   松弛成功时 cnt[v] = cnt[u] + 1；一旦 cnt[v] ≥ n，就说明这条路用了 n 条边 ——
//   必然重复经过某个点、绕了个环，而绕它还更短 → 负环。
//   （和 bell.cpp 那个「第 n 轮还能松弛」是同一个道理的两种记法。）
//   ⚠ 和 bell.cpp 一样，它天生只报告「从 s 能走到的」负环。
//
// ⚠ `inq[]` 的含义是「**它现在是不是正在队列里**」，不是「它来过没有」：
//   入队时置 1，**出队时必须清 0**。清晚了 / 忘了清，这个点就再也进不来了 ——
//   那就是 wrongSpfaInq.cpp。第 30 章「vis 要在入队时打」讲的是另一件事，别记混。
//
// 复杂度：**最坏还是 O(nm)**（它没有改变 Bellman-Ford 的上界，只是通常快很多）。
//   ⚠ 「SPFA 已死」这句话说的就是这件事：出题人可以专门造网格状的数据把它卡回最坏。
//   正文第 7 步用 count.cpp 把「白扫的边」这个数量出来了。

#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<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), cnt(n + 1, 0), inq(n + 1, 0);
    queue<int> q;
    dist[s] = 0;
    q.push(s); inq[s] = 1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = 0;                               // ⚠ 出队就得清，它说的是「在不在队里」
        for (auto [v, w] : g[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;              // ★ 这条路用了几条边
                if (cnt[v] >= n) { cout << "NEGATIVE\n"; return 0; }
                if (!inq[v]) { q.push(v); inq[v] = 1; }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] >= INF) cout << "x";
        else cout << dist[i];
        cout << " \n"[i == n];
    }
    return 0;
}

// ✗ 错误版本③ —— 不判「走不到」就去松弛。★ 这一次它真的会传染
//
// 和 bell.cpp 只差一句：
//
//     bell.cpp： if (dist[u] == INF) continue;      // 走不到的点不参与松弛
//     这里：     （删掉）                            // ✗
//
// ★★ 这一份是第 32 章那笔账的**正面回应**，值得单独停一下。
//
//   第 32 章我写过一个几乎一模一样的错误版本，然后被实测打脸：
//   那一章边权非负，`INF + w` 比 INF **大**，松弛条件 `dist[u] + w < dist[v]` 根本不成立，
//   所以「不判可达」在那里**一点事都没有**。
//
//   这一章边权可以是负的。`INF + (-7)` 比 INF **小** —— 那一句当场成立：
//
//       走不到的点，会被刷出一个「比 INF 小一点」的距离，然后顺着边一路传染出去。
//
//   ⚠ **同一句代码危不危险，取决于数据的取值范围。**
//     「这句判断是不是多余的」这种问题，没有脱离数据的答案。
//
// ⚠ 它还会顺带把负环判错：那些被污染的点让第 n 轮凭空多出可松弛的边，
//   于是它有时会对一张根本没有负环的图喊 NEGATIVE。**一个 bug 同时污染两种输出。**
//
// ★ 所以这一份是给**生成器**出的题：数据里必须有**从 s 走不到的点**
//   （第 30、32 章那条第三次登场），而且那些点之间还得有边，污染才传得开。

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

const int INF = 0x3f3f3f3f;

struct E { int u, v, w; };

int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<E> es(m);
    for (auto& e : es) cin >> e.u >> e.v >> e.w;

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

    for (int round = 1; round <= n - 1; round++) {
        for (auto [u, v, w] : es)
            if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;   // ✗ 没挡住走不到的点
    }

    for (auto [u, v, w] : es)
        if (dist[u] + w < dist[v]) { cout << "NEGATIVE\n"; return 0; }

    for (int i = 1; i <= n; i++) {
        if (dist[i] >= INF) cout << "x";
        else cout << dist[i];
        cout << " \n"[i == n];
    }
    return 0;
}

// ✗ 错误版本④ —— 判负环时不管「s 到底走不走得到它」
//
// 和 brute.cpp 只差半句：
//
//     brute.cpp： if (d[k][k] < 0 && d[s][k] < INF) → NEGATIVE
//     这里：      if (d[k][k] < 0)                  → NEGATIVE      // ✗ 少了后半句
//
// ★ 它错的不是算法，是**题面**：题目问的是「从 s 出发能不能走到负环」，
//   而 `d[k][k] < 0` 回答的是「图里有没有负环」。图的角落里躺着一个负环，
//   可 s 根本走不过去 —— 那道题的答案照样是一串距离，不是 NEGATIVE。
//
// ★★ 这一份最值钱的地方在于对照：
//
//     | | 「只算 s 能走到的」这件事 |
//     |---|---|
//     | Floyd（brute.cpp） | 要**手动补**一句 `d[s][k] < INF` —— 它算的是全图 |
//     | Bellman-Ford / SPFA | **白送** —— dist 从 s 初始化，走不到的点永远是 INF |
//
//   同一个题面，一个天生满足、一个必须自己补 ——
//   **这种地方最容易在两份代码之间写出不一致，而且两边各自看都「没毛病」。**
//   （第 19 章那条「题目对边界的约定要抄进注释」，这是图论版。）
//
// ⚠ 这一份是给**生成器**出的最刁的一道题：数据里得有「**s 走不到的负环**」。
//   而这要求两件事同时成立：图不连通（第 30、32 章那条），并且**孤立的那一块里有负环**。
//   正文第 9 步那张表里，它是最后一个从 0 变成非 0 的。

#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;
        d[u][v] = min(d[u][v], w);
    }

    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 k = 1; k <= n; k++)
        if (d[k][k] < 0) { cout << "NEGATIVE\n"; return 0; }    // ✗ 没问 s 走不走得到

    for (int i = 1; i <= n; i++) {
        if (d[s][i] >= INF) cout << "x";
        else cout << d[s][i];
        cout << " \n"[i == n];
    }
    return 0;
}

// ★ Bellman-Ford —— 负权的正经办法，也是这一章第二个关键一步
//
// 和 brute.cpp（Floyd）解同一道题，答案必须一模一样。
//
// ★ 一句话：**把所有边挨个松弛一遍，叫一轮；跑 n−1 轮就够了。**
//
//   为什么是 n−1，而且一轮不多一轮不少 —— 关键在这个不变量：
//
//       跑完第 i 轮之后，dist[v] ≤「从 s 出发、**最多走 i 条边**能到 v 的最短长度」
//
//   （归纳一行就完了：第 i 轮松弛边 (u,v) 时，dist[u] 已经不差于「最多 i−1 条边」的答案。）
//
//   而**没有负环时，最短路一定是一条简单路径** —— 它最多经过 n 个点、也就是 n−1 条边。
//   所以 n−1 轮之后一定收敛。★ 「n−1」不是背下来的，是「简单路径最多 n−1 条边」这句话。
//
// ★ 判负环是白送的（第 31 章「判环白送」的第二次）：
//
//       跑完 n−1 轮之后，**再跑一轮**。要是还有边能松弛成功 —— 有负环。
//
//   为什么：能松弛成功说明存在一条「用了 n 条边还更短」的走法，
//   n 条边的走法必然重复经过某个点，也就是绕了一个环，而绕它让距离变小 → 那是负环。
//
//   ⚠ 而且这份代码天生只报告「**从 s 能走到的**负环」：
//     dist 是从 s 初始化的，走不到的点永远是 INF，`if (dist[u] == INF) continue;` 会把它挡住。
//     ★ 对照 brute.cpp：Floyd 看的是全图，那个过滤必须自己补一句 `d[s][k] < INF`。
//     **同一个题面，两种算法一个天生满足、一个必须手动补** —— 这种地方最容易写出不一致。
//
// ⚠ `if (dist[u] == INF) continue;` 这一句在**负权图上是必须的**，不是保险：
//   `INF + (-7)` 比 INF 小，不挡住的话，走不到的点会被刷出一个「比 INF 小一点」的距离，
//   而且顺着边传染。第 32 章那个「以为会传染、实测不会」的坑，在这一章**真的会**发生 ——
//   因为那时边权非负。**同一句代码危不危险，取决于数据的取值范围。**
//
// 复杂度 O(nm)：n 轮，每轮扫 m 条边。比 Floyd 的 O(n³) 好在稀疏图上。

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

const int INF = 0x3f3f3f3f;

struct E { int u, v, w; };

int main() {
    int n, m, s;
    if (!(cin >> n >> m >> s)) return 0;
    vector<E> es(m);
    for (auto& e : es) cin >> e.u >> e.v >> e.w;

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

    // ★ n−1 轮就够了：没有负环时，最短路是简单路径，最多 n−1 条边
    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (auto [u, v, w] : es) {
            if (dist[u] == INF) continue;         // ⚠ 负权下这一句是必须的，见上面
            if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; changed = true; }
        }
        if (!changed) break;                      // 提前收敛了就不用跑满（不影响正确性）
    }

    // ★ 第 n 轮：还能松弛成功 ⇔ 从 s 能走到一个负环
    for (auto [u, v, w] : es) {
        if (dist[u] == INF) continue;
        if (dist[u] + w < dist[v]) { cout << "NEGATIVE\n"; return 0; }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] >= INF) cout << "x";
        else cout << dist[i];
        cout << " \n"[i == n];
    }
    return 0;
}