#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define dump(o) { cerr << #o << " " << o << endl; }
#define dumpc(o) { cerr << #o; for (auto e : (o)) cerr << " " << e; cerr << endl; }
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

//dx[i],dy[i]???i?????????????§???????????????¢???
//  3
// 2 0
//  1

//??\?????¨?????°
int X, Y;

//xy??§?¨???§?????±???????????¢?´¢
void dfs(int x, int y) {
	/* ?????? */
	//?§????4?????????????????????
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };
	//?§????4???????????¢?´¢
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (0 <= nx&&nx < X && 0 <= ny&&ny < Y) {
			dfs(nx, ny);
		}
	}
}

//xy??§?¨???§??????????????¢?´¢
//???????????¢
int bfs(int sx, int sy, int gx, int gy) {
	const int MAX = 1; //????????´???
	queue<pii> Q;
	Q.push(pii(sx, sy));
	//???????????¢
	int d[MAX][MAX];
	memset(d, 0x3f, sizeof(d));
	d[sx][sy] = 0;
	//?§????4?????????????????????
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };
	for (pii u; !Q.empty();) {
		u = Q.front(); Q.pop();
		if (u == pii(gx, gy))break; //??´??????????????¢?´¢????????????
		for (int i = 0; i < 4; i++) {//?§????4???????????¢?´¢
			int nx = u.first + dx[i], ny = u.second + dy[i];
			if (0 <= nx&&nx < X && 0 <= ny&&ny < Y) {
				if (d[nx][ny] != INF)continue; //??¢?´¢???????£???°???
				d[nx][ny] = d[u.first][u.second] + 1;
				Q.push(pii(nx, ny));
			}
		}
	}
	return d[gx][gy];
}

//??¶?´?????????£???????????? int:INF ll:INFL
#define INFG INFL
using Weight = ll;//int;

class Edge {
public:
	int s; //source
	int d; //destination
	Weight w; //weight
	Edge(int s = 0, int d = 0, Weight w = INFG) : s(s), d(d), w(w) {};
	bool operator<(const Edge &e)const { return w < e.w; }
};
using Edges = vector<Edge>;
//???????????\: g[u].push_back(Edge(u, v, c));
//????????¨???????????????????????°??????????????\?????????????????????
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

//?????¢?´¢, ??¢?´¢???, ??¢?´¢???
enum { WHITE, GRAY, BLACK };
//???????§?????????????(???????????????) Single Source Shortest Path
//Dijkstra O( |E|log|V| )
//dist: ?§????????????????????????§??????????????¢
//?????????: ???????????¨????????????(??????-1)
vector<int> dijkstra(const Graph &g, int s, vector<Weight> &dist) {
	typedef tuple<Weight, int, int> State; //?§?????????????????°?????????? ??? ???
	priority_queue<State, vector<State>, greater<State> >PQ;
	int n = g.size();
	vector<int> color(n, WHITE);
	vector<int> prev(n, -1);
	dist.assign(n, INFG); //distance
	dist[s] = 0; PQ.push(State(0, s, -1)); color[s] = GRAY; //?§????
	while (!PQ.empty()) {
		Weight d; int v; int u;
		tie(d, v, u) = PQ.top(); PQ.pop(); //dist???????°??????¨??????????´????????????????
		if (dist[v] < d) continue; //?????§???????????§???????????°??????
		color[v] = BLACK;
		prev[v] = u;
		for (auto e : g[v]) { //??£??\????????????????????¨????????????		
			if (color[e.d] == BLACK)continue; //??¢?´¢????????????
			if (dist[e.d] > dist[v] + e.w) {
				dist[e.d] = dist[v] + e.w;
				PQ.push(State(dist[e.d], e.d, v));
				color[e.d] = GRAY;
			}
		}
	}
	return prev;
}

//???????§?????????????(???????????????) Single Source Shortest Path
//Bellman Ford O(|V||E|)
//dist: ?§????????????????????????§??????????????¢
//prev: ???????????¨????????????
//?????????: ???????????????:true ??????:false
bool bellmanFord(const Graph &g, int s, vector<Weight> &dist, vector<int> &prev) {
	int n = g.size();
	Edges es; for (int i = 0; i < n; i++) for (auto &e : g[i]) es.emplace_back(e);
	dist.assign(n, INFG); dist[s] = 0;
	prev.assign(n, -1);
	bool negative_cycle = false;
	for (int i = 0;; i++) {
		bool update = false;
		for (auto &e : es) {
			if (dist[e.s] != INFG && dist[e.d] > dist[e.s] + e.w) {
				dist[e.d] = dist[e.s] + e.w;
				prev[e.d] = e.s;
				update = true;
			}
		}
		if (!update) break;
		if (i > n) { negative_cycle = true; break; }
	}
	return !negative_cycle;
}

//?§?????????????????????§??????????????????
//???????????????????????°?????????????§??????????????????§?????????????????¢????????????
vector<int> getPath(int s, int g, vector<int> prev) {
	vector<int> path;
	path.push_back(g);
	for (int i = g; i != s; ) path.push_back(i = prev[i]);
	reverse(path.begin(), path.end());
	return path;
}

//??¨????????????????????? All Pairs Shortest Path
//Warshall Floyd O(|V|^3)
//?????????: ???????????????:true ??????:false
bool warshallFloyd(const Graph &g, Matrix &dist) {
	bool negative_cycle = false;
	int n = g.size();
	dist.assign(n, Array(n, INFG));
	for (int i = 0; i < n; i++) dist[i][i] = 0;
	for (int i = 0; i < n; i++)
		for (auto e : g[i])
			dist[e.s][e.d] = min(dist[e.s][e.d], e.w);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				if (dist[j][i] != INFG&&dist[i][k] != INFG)
					dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
	for (int i = 0; i < n; i++)
		if (dist[i][i] != 0)
			negative_cycle = true;
	return !negative_cycle;
}

//???????????????
void printPath(vector<int> path) {
	cout << "Path: ";
	for (auto p : path) cout << p << " ";
	cout << endl;
}

//???????????????????????????
//??\?¬???°???0????????¨???????????????????????????ret????????£??????
vector<int> topologicalSort(const Graph &g) {
	int n = g.size(), k = 0;
	vector<int> ord(n), indeg(n); //??\?¬???°
	for (auto &es : g) for (auto &e : es) indeg[e.d]++;
	queue<int> Q;
	for (int i = 0; i < n; i++) if (indeg[i] == 0) Q.push(i);
	while (!Q.empty()) {
		int v = Q.front(); Q.pop(); ord[k++] = v;
		for (auto &e : g[v]) if (--indeg[e.d] == 0) Q.push(e.d);
	}
	return *max_element(indeg.begin(), indeg.end()) == 0 ? ord : vector<int>();
}

//??¨?????´???
Edge diameter(const Graph &g, int s = 0) {
	vector<Weight> dist;
	dijkstra(g, s, dist);
	int n = g.size(), u = -1, v = -1;
	for (int i = 0; i < n; i++) if (dist[i] != INFG && (u == -1 || dist[i] > dist[u])) u = i;
	dijkstra(g, u, dist);
	for (int i = 0; i < n; i++) if (dist[i] != INFG && (v == -1 || dist[i] > dist[v])) v = i;
	Weight d = dist[v];
	if (u > v) swap(u, v);
	return Edge(u, v, d);
}

//?´?????????????????§????
//Union-Find??¨
struct UnionFind {
	vector<int> p; //parent
	int s; //size ???????????°
	UnionFind(int n) :p(n, -1), s(n) {}
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return false;
		if (size(x) < size(y)) swap(x, y);
		p[x] += p[y]; p[y] = x; s--;
		return true;
	}
	bool same(int x, int y) { return root(x) == root(y); }
	int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
	//?????????????´???°
	int size(int x) { return -p[root(x)]; }
};

//????°???¨?????¨
//Kruskal O(|E|log|E|)
pair<Weight, Edges> kruskal(const Graph &g) {
	UnionFind UF(g.size());
	Edges es;
	for (int i = 0; i < g.size(); i++) for (auto &e : g[i]) es.emplace_back(e);
	sort(es.begin(), es.end());
	Weight total = 0;
	Edges T;
	for (auto &e : es) if (!UF.same(e.s, e.d)) {
		T.push_back(e); total += e.w; UF.unite(e.s, e.d);
	}
	return make_pair(total, T);
}

int main() {
	int V, E, r; cin >> V >> E >> r;
	Graph g(V);
	for (int i = 0; i < E; i++) {
		int s, t, d; scanf("%d%d%d", &s, &t, &d);
		g[s].push_back(Edge(s, t, d));
	}
	vector<Weight> dist;
	vector<int>prev;
	if (bellmanFord(g, r, dist, prev))
		for (auto &e : dist)
			if (e == INFG) cout << "INF" << endl;
			else cout << e << endl;
	else
		cout << "NEGATIVE CYCLE" << endl;
	return 0;
}

Measured memory_bytes: 3308