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

// Template Headers {{{
using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long; using vll = vector<long long>;
template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> istream &operator>>(istream &, vector<T> &);
template <class T> ostream &operator<<(ostream &, const vector<T> &);
template <class T, class U> istream &operator>>(istream &, pair<T, U> &);
template <class T, class U> ostream &operator<<(ostream &, const pair<T, U> &);
template <class T> struct Inf { static constexpr T inf() { return std::numeric_limits<T>::has_infinity() ? std::numeric_limits<T>::infinty() : std::numeric_limits<T>::max(); } };
template <> struct Inf<int> { static constexpr int inf() { return 0x3f3f3f3f; } };
template <> struct Inf<long long> { static constexpr long long inf() { return 0x3f3f3f3f3f3f3f3fLL; } };
constexpr int INF = Inf<int>::inf(); constexpr ll BINF = Inf<ll>::inf();
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// }}}
// Weighted Graph Template {{{
template <class T>
class WeGraph : public vector<vector<pair<int, T>>> {
	private:
		int n, m;
	public:
		WeGraph(int n, int m) : vector<vector<pair<int, T>>>(n), n(n), m(m) {}

		template <class U>
		friend istream &operator>>(istream &is, WeGraph<U> &g) {
			for (int i=0;i<g.m;i++) {
				int u, v; T l; is >> u >> v >> l; // u--, v--;
				g[u].emplace_back(v, l);
				// g[v].emplace_back(u, l); // comment out this line for undirected graph
			}
			return is;
		}

		void addDiEdge(int u, int v, const T &w) { (*this)[u].emplace_back(v, w); }
		void addDiEdge(int u, int v, T &&w) { (*this)[u].emplace_back(v, w); }

		void addEdge(int u, int v, const T &w) { addDiEdge(u, v, w), addDiEdge(v, u, w); }
		void addEdge(int u, int v, T &&w) { addDiEdge(u, v, w), addDiEdge(v, u, w); }

};
// }}}

int solve() {
	int n, m, r; cin >> n >> m >> r;
	WeGraph<ll> g(n, m); cin >> g;
	vi inQueue(n), visited(n);
	vll dist(n, BINF);
	dist[r] = 0;
	for (int i=0;i<n;i++) {
        for (int u=0;u<n;u++) {
            if (dist[u] >= BINF) continue;
        	for (auto p : g[u]) {
        		int v = p.first; ll l = p.second;
        		if (dist[u] + l < dist[v]) {
        		    dist[v] = dist[u] + l;
        		    if (i == n - 1) {
        			    cout << "NEGATIVE CYCLE" << endl;
        			    return 0;
        		    }
        		}
        	}
        }
	}
	for (int i=0;i<n;i++) {
		if (dist[i] == BINF)
			cout << "INF" << endl;
		else
			cout << dist[i] << endl;
	}

	return 0;
}

// Template Main {{{
int main() {
	ios::sync_with_stdio(0);
	// precompute();
	// int t; cin >> t; for (int i=1;i<=t;i++)
	solve();
	// cout << "Case #" << i << ": ", solve();
	return 0;
}

template <class T> istream &operator>>(istream &is, vector<T> &v) {
	for (auto it=v.begin();it!=v.end();++it) is >> *it;
	return is;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	for (auto it=v.begin();it!=v.end();) os << *it, os << " \n"[++it==v.end()];
	return os;
}

template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) {
	return is >> p.first >> p.second;
}

template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) {
	return os << p.first << ' ' << p.second;
}
// }}}

// vim: fdm=marker



Measured memory_bytes: 3276