#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4; // 足够大，plus 操作不会溢出

struct Edge {
    int u, v;
    ll w;
    Edge(int _u=0, int _v=0, ll _w=0) : u(_u), v(_v), w(_w) {}
};

/*
 * Bellman-Ford 竞赛模板
 *
 * 输入：
 *   n : 顶点数 (0..n-1)
 *   m : 边数
 *   接下来 m 行，每行 u v w （表示 u -> v 的边权为 w）
 *   s : 源点
 *
 * 输出（模板示例）：
 *   对每个顶点 i：
 *     - 若 i 不可达： 输出 "INF"
 *     - 若 i 可达并且受负环影响（距离可任意减小）： 输出 "-INF"
 *     - 否则 输出最短距离 dist[i]
 *
 * 另外提供 reconstruct_path(s, t, prev) 重建单源到 t 的一条最短路径（若可重建）
 *
 * 复杂度：O(n * m)
 */

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<Edge> edges;
    edges.reserve(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        // 若输入为 1-index，请在此处做 --u; --v;
        edges.emplace_back(u, v, w);
    }

    int s;
    cin >> s; // 源点

    // ---------- Bellman-Ford 主体 ----------
    vector<ll> dist(n, INF);
    vector<int> prev(n, -1); // 用于路径重建
    dist[s] = 0;

    // 1) 做 n-1 轮松弛，使 dist 收敛（若无负环）
    for (int iter = 0; iter < n - 1; ++iter) {
        bool updated = false;
        for (const auto &e : edges) {
            if (dist[e.u] != INF && dist[e.v] > dist[e.u] + e.w) {
                dist[e.v] = dist[e.u] + e.w;
                prev[e.v] = e.u;
                updated = true;
            }
        }
        if (!updated) break; // 提前退出（常见优化）
    }

    // 2) 检测并标记受负环影响的节点
    // nodes_in_neg_cycle[i] == true 表示 i 的距离可以无限减小
    vector<char> in_neg(n, 0);

    // 第 n 轮：若还能松弛则相关节点受负环影响（或者能从某个负环传播到）
    // 我们先把可以被松弛的点入队，然后在图上做 BFS/DFS 向外传播（因为负环的影响会沿有向边传播到可达节点）
    queue<int> q;
    for (const auto &e : edges) {
        if (dist[e.u] != INF && dist[e.v] > dist[e.u] + e.w) {
            // e.v 受影响（直接）
            if (!in_neg[e.v]) {
                in_neg[e.v] = 1;
                q.push(e.v);
            }
        }
    }

    // 为了传播负环影响，需要图的邻接表（从受影响节点向外传播）
    vector<vector<int>> adj_out(n);
    for (const auto &e : edges) {
        adj_out[e.u].push_back(e.v);
    }

    // BFS/DFS 从初始受影响节点传播，标记所有可达顶点为受影响
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int y : adj_out[x]) {
            if (!in_neg[y]) {
                in_neg[y] = 1;
                q.push(y);
            }
        }
    }

    // ---------- 输出结果示例 ----------
    // 若想要标准竞赛输出：可根据题目要求调整输出格式
    // 下面按通用风格输出每个顶点的状态
    for (int i = 0; i < n; ++i) {
        if (in_neg[i]) {
            cout << "-INF";        // 受负环影响，可以任意小
        } else if (dist[i] == INF) {
            cout << "INF";         // 不可达
        } else {
            cout << dist[i];       // 有确定的最短距离
        }
        if (i + 1 < n) cout << ' ';
    }
    cout << '\n';

    // ---------- 可选：重建单源到某个 t 的路径（前提：t 不受负环影响且可达） ----------
    // 示例：如果输入了一个 t，则输出路径
    int t;
    if (cin >> t) {
        if (in_neg[t]) {
            cout << "Target node " << t << " is affected by a negative cycle; path undefined.\n";
        } else if (dist[t] == INF) {
            cout << "No path from " << s << " to " << t << '\n';
        } else {
            vector<int> path;
            for (int cur = t; cur != -1; cur = prev[cur]) {
                path.push_back(cur);
            }
            reverse(path.begin(), path.end());
            cout << "Path: ";
            for (int x : path) cout << x << ' ';
            cout << '\n';
        }
    }

    return 0;
}