#include<bits/stdc++.h>
using namespace std;
#define INF INT_MAX
typedef pair<int, int> P;
int main(void){
	int v, e, r;
	cin >> v >> e >> r;
	int from[e], to[e], cost[e], sum = 0;
	for(int i = 0; i < e; i++) cin >> from[i] >> to[i] >> cost[i];
	int leng[v];
	fill(leng, leng + v, INF);
	leng[r] = 0;
	int i, upd;
	for(i = 0; i < v; i++){
		upd = 0;
		for(int j = 0; j < e; j++){
			int f = from[j], t = to[j], c = cost[j];
			if(leng[f] != INF && leng[t] > leng[f] + c) leng[t] = leng[f] + c, upd = 1;
		}
		if(!upd) break;
	}
	if(i == v && upd) cout << "NEGATIVE CYCLE" << endl;
	else {
		for(int i = 0; i < v; i++){
			if(leng[i] == INF) cout << "INF" << endl;
			else cout << leng[i] << endl;
		}
	}
	return 0;
}
