#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define IOS cin.tie(0),ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline ostream& operator << (ostream& out, const vector<T>& v) {
    if (v.empty())return out;
    constexpr bool is_vector_v = is_vector<T>::value;
    if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
    else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
    return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

class BellmanFord {
public:
    struct edge {
        int to;
        ll cost;
        edge(int to, ll cost) : to(to), cost(cost) {}
    };
    struct node {
        int from;
        ll cost;
        node(int from, ll cost) : from(from), cost(cost) {}
    };
    vector<vector<edge>> path;
    int n;
    ll inf = LLONG_MAX / 2;
    
    BellmanFord(int n) :n(n) {
        path.resize(n);
    }
    void push_edge(int a, int b, ll c) {
        path[a].push_back(edge(b, c));
    }
    vector<node> solve(int start) {
        vector<node> dist(n, node(-1, inf));
        dist[start].cost = 0;
        REP(i, this->n - 1) {
            REP(j, this->n) {
                REP(k, path[j].size()) {
                    if (dist[j].cost != this->inf) {
                        if (chmin(dist[path[j][k].to].cost, dist[j].cost + path[j][k].cost)) {
                            dist[path[j][k].to].from = j;
                        }
                    }
                }
            }
        }
        REP(i, this->n - 1) {
            REP(j, this->n) {
                REP(k, path[j].size()) {
                    int from = j;
                    int to = path[j][k].to;
                    ll cost = path[j][k].cost;
                    if (dist[to].cost != this->inf && dist[from].cost + cost < dist[to].cost) {
                        dist[to].cost = -this->inf;
                    }
                    if (dist[from].cost==-this->inf) {
                        dist[to].cost = -this->inf;
                    }
                }
            }
        }
        return dist;
    }
    vector<int> restore(vector<node>& dist, int end) {
        vector<int> res;
        if (dist[end].cost == -this->inf || dist[end].cost == this->inf) {
            return res;
        } else {
            int now = end;
            while (now >= 0) {
                res.push_back(now);
                now = dist[now].from;
            }
            reverse(res.begin(), res.end());
            return res;
        }
    }
};

int main() {
    IOS;
    int n, m, r;
    cin >> n >> m >> r;
    vector<ll> a(m), b(m), c(m);
    BellmanFord bf(n);
    REP(i, m) {
        cin >> a[i] >> b[i] >> c[i];
        //a[i]--;
        //b[i]--;
        bf.push_edge(a[i], b[i], c[i]);
    }
    int start = r;
    auto dist = bf.solve(start);
    REP(i, n) {
        int end = i;
        if (dist[end].cost==-bf.inf) {
            put("NEGATIVE CYCLE");
            return 0;
        }
    }
    REP(i, n) {
        int end = i;
        if (dist[end].cost == bf.inf) {
            put("INF");
        } else {
            put(dist[end].cost);
            //put(bf.restore(dist, end));
        }
        
    }
    return 0;
}



Measured memory_bytes: 3252