#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

struct node {
  int id;
  int weight;
  struct node *next;
};
struct node **list;
long int *pass, *dist;

void Insert(int, int, int);
int Bellman(int, int, int);

int main(void)
{
  int i, v, e, r, s, t, d;
  scanf("%d %d %d", &v, &e, &r);
  pass = (long int*)malloc(sizeof(long int) * v);
  dist = (long int*)malloc(sizeof(long int) * v);
  list = (struct node**)malloc(sizeof(struct node*) * v);
  for (i = 0; i < v; i++) list[i] = NULL;
  for (i = 0; i < e; i++) {
    scanf("%d %d %d", &s, &t, &d);
    Insert(s,t,d);
  }
  if (Bellman(r, v, e) == 1) {
    for (i = 0; i < v; i++) {
      if (dist[i] == INT_MAX) printf("INF\n");
      else printf("%ld\n", dist[i]);
      free(list[i]);
    }
  } else {
    printf("NEGATIVE CYCLE\n");
    for (i = 0; i < v; i++) {
      free(list[i]);
    }
  }
  free(pass);
  free(dist);
  free(list);
  return 0;
}

void Insert(int a, int b, int weight)
{
  struct node *p = (struct node*)malloc(sizeof(struct node));
  p->id = b;
  p->weight = weight;
  p->next = list[a];
  list[a] = p;
}

int Bellman(int p, int size, int esize)
{
  int i;
  for (i = 0; i < size; i++){
    dist[i] = INT_MAX;
    pass[i] = 0;
  }
  dist[p] = 0;
  while (1) {
    int flag = 0;
    for (i = 0; i < size; i++){
      struct node *n;
      if (dist[i] == INT_MAX) continue;
      for (n = list[i]; n != NULL; n = n->next) {
        int w = n->weight;
        if (w + dist[i] < dist[n->id]) {
          dist[n->id] = w + dist[i];
          pass[n->id]++;
          if (pass[n->id] >= esize) {
            return 0;
          }
          flag = 1;
        }
      }
    }
    if (!flag) break;
  }
  return 1;
}
