#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
using P = pair<int, int>;
constexpr int INF = 1000000000 + 8;

class Graph {
   private:
    struct edge {
        int to;
        int cost;
        edge(int i, int c) : to(i), cost(c) {}
    };
    vector<vector<edge>> edges;
    vector<int> dists;

   public:
    Graph(int n) { edges.resize(n); };
    int size() const { return edges.size(); };
    int countEdge() const {
        int count = 0;
        for (auto &&i : edges)
            for (auto &&j : i) count++;
        return count;
    }
    void addDirectedEdge(int from, int to, int cost) {
        edges[from].push_back(edge(to, cost));
    }
    void addEdge(int from, int to, int cost) {
        addDirectedEdge(from, to, cost);
        addDirectedEdge(to, from, cost);
    }

    void dijkstrta(int s) {
        dists.assign(size(), INF);
        priority_queue<P, vector<P>, greater<P>> pq;
        pq.push({0, s});
        dists[s] = 0;

        while (!pq.empty()) {
            // 仮の最短距離と頂点の集合のうち、最短距離が最小の頂点を「最短距離が確定した頂点」とする
            int p = pq.top().second, p_dists = pq.top().first;
            pq.pop();
            // ある経路で仮の最短距離と頂点の集合に追加されたが、別の経路で「最短距離が確定した頂点」は更新しない
            if (dists[p] < p_dists) continue;

            // 「最短距離が確定した頂点」と隣接した頂点の最短距離を更新する
            for (auto &&edge : edges[p]) {
                const int np = edge.to;
                const int cost = edge.cost;
                if (dists[np] > dists[p] + cost) {
                    dists[np] = dists[p] + cost;
                    // 仮の最短距離と頂点の集合に追加する
                    pq.push({dists[np], np});
                }
            }
        }
    }
    // bellmanford
    // 頂点sの最短距離を更新する
    // 負の経路があればtrueを返す
    bool bellmanford(int s) {
        dists.assign(size(), INF);
        dists[s] = 0;
        bool update;
        // |V|回探索する
        for (int i = 0; i < size(); i++) {
            update = false;
            // すべての辺について最短距離を更新する
            for (int j = 0; j < size(); j++) {
                for (auto &&edge : edges[j]) {
                    const int from = j, to = edge.to;
                    if (dists[to] > dists[from] + edge.cost) {
                        dists[to] = dists[from] + edge.cost;
                        update = true;
                    }
                }
            }
        }
        // |V|回目の探索で最短距離が更新されたなら負の経路が存在する
        return update;
    }
    int distance(int i) const { return dists[i]; }
    // rから辿りつけない辺を削除する
    void removeUnusedEdges(int s) {
        stack<int> stk;
        stk.push(s);

        vector<vector<edge>> new_edges;
        new_edges.resize(size());

        while (!stk.empty()) {
            const int p = stk.top();
            stk.pop();
            for (auto &&edge : edges[p]) {
                const int np = edge.to;

                bool used = false;
                for (auto &&i : new_edges[p]) {
                    if (edge.to == i.to) used = true;
                }

                if (!used) {
                    stk.push(np);
                    new_edges[p].push_back(edge);
                }
            }
        }

        edges = new_edges;
    }
};

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m, s;
    cin >> n >> m >> s;

    Graph g(n);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        g.addDirectedEdge(u, v, w);
    }

    g.removeUnusedEdges(s);
    if (g.bellmanford(s)) {
        cout << "NEGATIVE CYCLE" << endl;
    } else {
        for (int i = 0; i < n; i++) {
            const int dist = g.distance(i);
            cout << (dist < INF ? to_string(dist) : "INF") << endl;
        }
    }
}



Measured memory_bytes: 3420