#include <stdio.h>          // printf(), scanf()
#include <stdbool.h>

#define MAX_V 1000
#define MAX_E 2000
#define INF 100000000

typedef struct edge_tbl
{
	int from;
	int to;
	int cost;
} edge;

edge es[MAX_E];
int V, E;

void
bellman_ford(int s)
{
	int d[MAX_V];
	int i, j;

	for (i = 0; i < V; ++i)
		d[i] = INF;

	d[s] = 0;
	i = 0;
	while (true)
	{
		bool update = false;
		for (j = 0; j < E; ++j)
		{
			edge e = es[j];
			if (d[e.from] != INF && d[e.from] + e.cost < d[e.to])
			{
				d[e.to] = d[e.from] + e.cost;
				update = true;
				if (i == V - 1)
				{
					printf("NEGATIVE CYCLE\n");
					return;
				}
			}
		}

		if (!update)
			break;

		i++;
	}

	for (i = 0; i < V; ++i)
	{
		if (d[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", d[i]);
	}
}

int
main(int argc, char** argv)
{
	int r;
	int s, t, d;
	int i;

	scanf("%d %d %d", &V, &E, &r);
	for (i = 0; i < E; ++i)
	{
		scanf("%d %d %d", &s, &t, &d);
		es[i].from = s;
		es[i].to = t;
		es[i].cost = d;
	}

	bellman_ford(r);
	return 0;
}