#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <tuple>
#include <queue>
 
#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
using lli = long long int;

template <class DistanceType = int>
class BellmanFord{
private:
    using LLI = long long int;
    // 無限大 の距離
    const long long int infinity_cost = 9e18 + 1;
    int E; // 辺の数
    const int V; // 頂点数
    // u -> v in cost <=> (u, v, cost)
    using Node_Type = std::tuple<int, int, DistanceType>;
    std::vector<Node_Type> Nodes; //
    std::vector<LLI> Distances; // 距離を表す配列
    std::vector<bool> Connected; // 連結であるかを示す配列
    std::vector<bool> rConnected; // 逆向きから見て連結であるか
    // a -> b の重みなし辺 : In[b] = a, Out[a] = b
    std::vector<std::vector<int>> In, Out;
public:
    // コンストラクタ
    BellmanFord(int VN): V(VN){
        E = 0; Nodes.resize(0); Distances.resize(VN);
        Connected.resize(VN); rConnected.resize(VN);
        In.resize(VN, std::vector<int>(0));
        Out.resize(VN, std::vector<int>(0));
    }
    void add(int u, int v, DistanceType cost){
        Nodes.emplace_back(Node_Type(u, v, cost)); E++;
        In[v].push_back(u); Out[u].push_back(v);
    }

    // 頂点 startVer からの 頂点 endVerまでの最短距離を求める : -> distanceメソッドで値を取得
    // その経路の中で負の閉路による無限ループを検知したらfalseを返す
    bool computeBetween(int startVer, int endVer){
        // 無限大の距離
        std::fill(Distances.begin(), Distances.end(), infinity_cost);
        // 開始頂点から繋がっているかの情報
        std::fill(Connected.begin(), Connected.end(), false); 
            Connected[startVer] = true;
            std::queue<int> Que; Que.push(startVer);
            while(not Que.empty()){
                int v = Que.front(); Que.pop();
                for(int nv : Out[v]){
                    if(not Connected[nv]){
                        Connected[nv] = true;
                        Que.push(nv);
                    }
                }
            }

        // 終了頂点から繋がっているかの情報
        std::fill(rConnected.begin(), rConnected.end(), false);
            rConnected[endVer] = true;
            // 逆向き辺を用いてbfs
            Que.push(endVer);
            while(not Que.empty()){
                int v = Que.front(); Que.pop();
                for(int nv : In[v]){
                    if(not rConnected[nv]){
                        rConnected[nv] = true;
                        Que.push(nv);
                    }
                }
            }

        int u, v; DistanceType cost;
        Distances[startVer] = 0;
        // ループ ; 1 ~ V-1 回目 : 連結なもののみ更新を行う
        for(int loop = 0; loop < V - 1; loop++){
            for(int nodeLoop = 0; nodeLoop < E; nodeLoop++){
                std::tie(u, v, cost) = Nodes[nodeLoop]; 
                if(Distances[u] != infinity_cost and Distances[u] + cost < Distances[v]){
                    Distances[v] = Distances[u] + cost; Connected[v] = true;
                }
            }
        }

        // 頂点数 V 回目 ~> 負の閉路検出
        for(int nodeLoop = 0; nodeLoop < E; nodeLoop++){
            std::tie(u, v, cost) = Nodes[nodeLoop];
            if(Connected[v] and rConnected[v] and (Distances[u] + cost < Distances[v])) return false;
        }
        return true;
    }

    // 頂点 vertex からの最短距離を求める : 負の閉路による無限ループを検知したらfalseを返す
    //                                 (なお, 検出範囲を頂点と連結なもののみに制限している by Connected)
    bool computeAround(int vertex){
        // 無限大の距離
        std::fill(Distances.begin(), Distances.end(), infinity_cost);
        // 開始頂点から繋がっているかの情報
        std::fill(Connected.begin(), Connected.end(), false); 
            Connected[vertex] = true;
            std::queue<int> Que; Que.push(vertex);
            while(not Que.empty()){
                int v = Que.front(); Que.pop();
                for(int nv : Out[v]){
                    if(not Connected[nv]){
                        Connected[nv] = true;
                        Que.push(nv);
                    }
                }
            }


        int u, v; DistanceType cost;
        Distances[vertex] = 0;
        // ループ ; 1 ~ V-1 回目 : 連結なもののみ更新を行う
        for(int loop = 0; loop < V - 1; loop++){
            for(int nodeLoop = 0; nodeLoop < E; nodeLoop++){
                std::tie(u, v, cost) = Nodes[nodeLoop]; 
                if(Distances[u] != infinity_cost and Distances[u] + cost < Distances[v]){
                    Distances[v] = Distances[u] + cost; Connected[v] = true;
                }
            }
        }

        // 頂点数 V 回目 ~> 負の閉路検出
        for(int nodeLoop = 0; nodeLoop < E; nodeLoop++){
            std::tie(u, v, cost) = Nodes[nodeLoop];
            if(Connected[v] and (Distances[u] + cost < Distances[v])) return false;
        }
        return true;
    }

    // 繋がっているか, 連結であるかを返す
    bool isConnected(int vertex){
        return Connected.at(vertex);
    }

    // 距離を返す関数 
    long long int distance(int vertex){
        return Distances.at(vertex);
    }

};


int main(void){
    int n, m, r; scanf("%d%d%d", &n, &m, &r);
    BellmanFord<int> BF(n);
    REP(i, m){
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        BF.add(a, b, c);
    }
    if(BF.computeAround(r)){
        REP(i, n){
            if(BF.isConnected(i)) printf("%lld\n", BF.distance(i));
            else puts("INF");
        }
    }
    else puts("NEGATIVE CYCLE");


    return 0;
}



Measured memory_bytes: 3356