#include <iostream>
#include <math.h>

//#include "exp/fastio.hpp"
#include <cstdint>

typedef uint32_t u32;

#include <stdint.h>

typedef uint8_t  u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t   s8;
typedef int16_t  s16;
typedef int32_t  s32;
typedef int64_t  s64;

const int INF = (1 << 28);
const long INFL = (1LL << 50);

class void_ {
};

template<typename T>
class Weight {
protected:
  T w_;
public:
  const T& weight() const;
};

template<>
class Weight<void_> : public void_ {
};

template<typename Tweight>
const Tweight& Weight<Tweight>::weight() const {
  return w_;
}

template<typename Tweight>
class Edge : public Weight<Tweight> {
public:
  Edge();
  Edge(u32 from, u32 to);
  Edge(u32 from, u32 to, Tweight w);
  const u32& from() const;
  const u32& to() const;
  Edge reverse();
  void dump();
private:
  u32 s, t;
};

template<typename Tweight>
Edge<Tweight>::Edge() {
}

template<typename Tweight>
Edge<Tweight>::Edge(u32 from, u32 to) {
  s = from; t = to;
}

template<typename Tweight>
Edge<Tweight>::Edge(u32 from, u32 to, Tweight w) {
  s = from; t = to;
  this->w_ = w;
}

template<typename Tweight>
const u32& Edge<Tweight>::from() const {
  return s;
}

template<typename Tweight>
const u32& Edge<Tweight>::to() const {
  return t;
}

template<typename Tweight>
Edge<Tweight> Edge<Tweight>::reverse() {
  Edge res = *this;
  u32 tmp;
  tmp = s; s = t; t = tmp;
  return res;
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
class Graph {
public:
  Graph();
  Graph(u32 V);
  void insert(u32 s, u32 t, Tweight w);
  void insert(Edge<Tweight> edge);
  u32 Vsize() const;
  u32 Esize() const;
  Edge<Tweight> edge(u32 i) const;
  void activate();
  Edge<Tweight>* adjust(u32 v);
  u32 adjust_size(u32 v);
private:
  Edge<Tweight> edge_[maxE];
  u32 edge_num;
  u32 vertex_num;
  u32 adjust_size_[maxV];
  u32 index[maxV];
};

template<typename T, typename U>
T Max(T arg1, U arg2) {
  T arg2T = static_cast<T>(arg2);
  if( arg1 < arg2T ) return arg2T;
  return arg1;
}

template<typename T, typename U>
T Min(T arg1, U arg2) {
  T arg2T = static_cast<T>(arg2);
  if( arg2T < arg1 ) return arg2T;
  return arg1;
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
Graph<Tweight, isdirected, maxV, maxE>::Graph() {
  edge_num = 0;
  vertex_num = 0;
  for(int i = 0; i < maxV; ++i) {
    adjust_size_[i] = 0;
    index[i] = 0;
  }
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
Graph<Tweight, isdirected, maxV, maxE>::Graph(u32 V) {
  edge_num = 0;
  vertex_num = V;
  for(int i = 0; i < maxV; ++i) {
    adjust_size_[i] = 0;
    index[i] = 0;
  }
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
void Graph<Tweight, isdirected, maxV, maxE>::insert(Edge<Tweight> edge) {
  edge_[edge_num] = edge;
  edge_num += 1;
  if( not isdirected ) {
    edge_[edge_num] = edge.reverse();
    edge_num += 1;
  }
  vertex_num = Max(vertex_num, edge.from());
  vertex_num = Max(vertex_num, edge.to());
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
void Graph<Tweight, isdirected, maxV, maxE>::insert(u32 s, u32 t, Tweight w) {
  insert(Edge<Tweight>(s, t, w));
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
void Graph<Tweight, isdirected, maxV, maxE>::activate() {
  Edge<Tweight> buffer[maxE];
  u32 E = edge_num;
  u32 count[maxV];
  for(int i = 0; i < maxV; ++i) count[i] = 0;
  for(int i = 0; i < E; ++i) {
    count[edge_[i].from()] += 1;
  }
  for(int i = 0; i < maxV; ++i) {
    adjust_size_[i] = count[i];
  }
  int t = 0;
  for(int i = 0; i < maxV; ++i) {
    t += count[i];
    count[i] = t - count[i];
    index[i] = count[i];
  }
  for(int i = 0; i < E; ++i) {
    buffer[count[edge_[i].from()]] = edge_[i];
    count[edge_[i].from()] += 1;
  }
  for(int i = 0; i < E; ++i) {
    edge_[i] = buffer[i];
  }
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
Edge<Tweight>* Graph<Tweight, isdirected, maxV, maxE>::adjust(u32 v) {
  return &edge_[index[v]];
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
u32 Graph<Tweight, isdirected, maxV, maxE>::adjust_size(u32 v) {
  return adjust_size_[v];
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
u32 Graph<Tweight, isdirected, maxV, maxE>::Vsize() const {
  return vertex_num;
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
u32 Graph<Tweight, isdirected, maxV, maxE>::Esize() const {
  return edge_num;
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
Edge<Tweight> Graph<Tweight, isdirected, maxV, maxE>::edge(u32 i) const {
  return edge_[i];
}

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
bool Bellman_Ford(const Graph<Tweight, isdirected, maxV, maxE>& graph, u32 s, Tweight dist[]);

template<typename Tweight, bool isdirected, u32 maxV, u32 maxE>
bool Bellman_Ford(const Graph<Tweight, isdirected, maxV, maxE>& graph, u32 s, Tweight dist[]) {
  for(int i = 0; i < graph.Vsize(); ++i) dist[i] = INF;
  dist[s] = 0;
  for(int i = 0; i < graph.Vsize(); ++i) {
    bool update = false;
    for(int j = 0; j < graph.Esize(); ++j) {
      auto edge = graph.edge(j);
      if( dist[edge.from()] != INF && dist[edge.to()] > dist[edge.from()] + edge.weight()) {
        dist[edge.to()] = dist[edge.from()] + edge.weight();
        update = true;
        if( i == graph.Vsize() - 1) return false;
      }
    }
    if( not update ) break;
  }
  return true;
}
         

class Solver {
private:
public:
  void solve() {
    int V, E, r; std::cin >> V >> E >> r;
    Graph<long, true, 2000, 3000> graph(V);
    for(int i = 0; i < E; ++i) {
      int s, t, d; std::cin >> s >> t >> d;
      graph.insert(s, t, d);
    }
    graph.activate();
    long dist[2000];
    if( not Bellman_Ford(graph, r, dist) ) {
      std::cout << "NEGATIVE CYCLE" << std::endl;
      return;
    }
    for(int i = 0; i < (int)graph.Vsize(); ++i) {
      if( dist[i] == INF ) {
        std::cout << "INF" << std::endl;
      }
      else {
        std::cout << dist[i] << std::endl;
      }
    }
  }
};

int main() {

  Solver solver;
  solver.solve();
  
  return 0;
}

Measured memory_bytes: 3176