#include<vector>
#include<iostream>
using namespace std;
#define MAX_V 1000
#define MAX_E 2000
#define INF 1e9
struct edge {
	int from, to, cost;
};
int V, E, d[MAX_V];
edge es[MAX_E];
bool find_negative_loop(int s)
{
	int count=0;
	for (int i = 0; i < V; i++)
	{
		d[i] = INF;
	}
	d[s] = 0;
	while (true)
	{
		bool update = false;
		count++;
		for (int i = 0; i < E; i++)
		{
			if (d[es[i].from] != INF && d[es[i].to] > d[es[i].from] + es[i].cost)
			{
				if (count == V)
				{
					return true;
				}
				d[es[i].to] = d[es[i].from] + es[i].cost;
				update = true;
			}
		}
		if (!update)
		{
			break;
		}

	}
	return false;
}

int main()
{
	int r;
	cin >> V >> E >> r;
	for (int i = 0; i < E; i++)
	{
		cin >> es[i].from >> es[i].to >> es[i].cost;
	}
	if (find_negative_loop(r))
	{
		cout << "NEGATIVE CYCLE" << endl;
	}
	else
	{
		for (int i = 0; i < V; i++)
		{
			if (d[i] ==INF)
			{
				cout << "INF" << endl;
			}
			else
			{
				cout << d[i] << endl;
			}
		}
	}
	return 0;

	
}



