#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include<functional>
#include<queue>
#include<regex>
#include<time.h>
#include<type_traits>

using namespace std;
using ll = long long;

constexpr ll MOD = 1000000007;
constexpr ll INF = 1050000000;
constexpr ll LONGINF = 1050000000000000000;

struct all_init { all_init() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(15); }; }ALL_INIT;
struct edge { ll from, to, cost; bool operator < (const edge& x) const { return cost < x.cost; } };

#define CIN(vector_array_etc,n) for(int loop=0;loop<n;loop++){cin>>vector_array_etc[loop];};
#define COUT(vector_array_etc,n) for(int LOOP=0;LOOP<n;LOOP++){cout<<vector_array_etc[LOOP]<<(LOOP == n-1 ?'\n':' ');};
#define VC(Type_name) vector<Type_name>//1次元ならあまり意味ないかも
#define VCVC(Type_name) vector<vector<Type_name>>//2次元配列定義怠過ぎ問題
#define SORT(vector_etc) sort(vector_etc.begin(),vector_etc.end());

template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }//aに最大値が入る
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }//aに最小値が入る
template<class T>void swap(T &a, const T &b) { T tmp = a; a = b; b = a; return; }//aとbを入れ替える

template<typename T>
istream& operator >> (istream& is, vector<T>& Vec) { for (T& x : Vec) { is >> x; }return is; }

template<typename V, typename H>
void resize(vector<V>& vec, const H head) { vec.resize(head); }

template<typename V, typename H, typename ... T>
void resize(vector<V>& vec, const H& head, const T ... tail) { vec.resize(head); for (auto& v : vec) { resize(v, tail...); } }

int dx[] = { 0,1,-1, 0,1,-1, 1,-1 };    //i<4:4way i<8:8way
int dy[] = { 1,0, 0,-1,1,-1,-1, 1 };

class UnionFind {
private:
	std::vector<int> parent;
	std::vector<int> height;
	std::vector<int> m_size;

public:
	UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
		for (int i = 0; i < size_; ++i) parent[i] = i;
	}
	void init(int size_) {
		parent.resize(size_);
		height.resize(size_, 0);
		m_size.resize(size_, 1);
		for (int i = 0; i < size_; ++i) parent[i] = i;
	}
	int find(int x) {
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		int t = size(x) + size(y);
		m_size[x] = m_size[y] = t;
		if (height[x] < height[y]) parent[x] = y;
		else parent[y] = x;
		if (height[x] == height[y]) ++height[x];
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		if (parent[x] == x) return m_size[x];
		return size(parent[x] = find(parent[x]));
	}
};

//第一引数:始点
//第二引数:辺の数
//第三引数:頂点数
//第四引数:辺の重み付きのグラフ
//第五引数:各頂点への距離を入れる配列(答えが入る)
bool Bellman_Ford(int start, int E, int V, vector<edge> Edge, vector<ll> &d) {//V:頂点数 E:辺数 
	fill(d.begin(), d.end(), LONGINF);
	d[start] = 0;
	vector<bool> t(V, false);
	/*
	for (int i = 0; i < V - 1; i++) {
		for (int j = 0; j < E; j++) {
			edge e = Edge[j];
			if (d[e.from] == LONGINF) { continue; }
			if (d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
			}
		}
	}
	*/

	for (int i = 0; i < V; i++) {
		for (int j = 0; j < E; j++) {
			edge e = Edge[j];
			if (d[e.from] == LONGINF) { continue; }
			if (d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				t[e.to] = true;
				if (i == V - 1) {//どこかに閉路があることを感知する
					return false;
				}
			}
			if (t[e.from]) {
				t[e.to] = true;
			}
		}
	}
	/*
	if (t[V - 1]) {
	//V-1は頂点番号n-1で、始点からn-1までに負の閉路を検出したい場合には、
	//コメントアウトを解除すること。
		return false;
	}
	*/
	return true;
}

int main() {
	int n, m, r; cin >> n >> m >> r;
	vector<vector<int>> g(n);
	vector<edge> e(m);

	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		g[a].emplace_back(b);
		e[i].from = a;
		e[i].to = b;
		e[i].cost = c;
	}
	vector<ll> d(n);
	if (Bellman_Ford(r, m, n, e, d)) {//閉路検出(無限ループでinf)なし
		for (auto x : d) {
			if (x != LONGINF) {
				cout << x << endl;
			}
			else {
				cout << "INF" << endl;
			}
		}
	}
	else {//閉路検出した
		cout << "NEGATIVE CYCLE" << endl;
	}

	return 0;
}


Measured memory_bytes: 3256