#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

template <class T>
class graph {
 public:
  graph(int n) : n_(n) { data_.resize(n_); }
  struct edge {
    int from, to;
    T cost;
  };
  int n_;
  std::vector<std::vector<int>> data_;
  std::vector<edge> edges_;

  virtual void add(int from, int to, T cost) = 0;
};

template <class T>
class forest : public graph<T> {
 public:
  using graph<T>::n_;
  using graph<T>::data_;
  using graph<T>::edges_;

  forest(int n) : graph<T>(n) {}

  void add(int from, int to, T cost = 1) {
    int id = edges_.size();
    assert(id < n_ - 1);
    data_[from].emplace_back(id);
    data_[to].emplace_back(id);
    edges_.push_back({from, to, cost});
  }
};

template <class T>
class digraph : public graph<T> {
 public:
  using graph<T>::n_;
  using graph<T>::data_;
  using graph<T>::edges_;

  digraph(int n) : graph<T>(n) {}

  void add(int from, int to, T cost = 1) {
    int id = edges_.size();
    data_[from].emplace_back(id);
    edges_.push_back({from, to, cost});
  }

  digraph<T> reverse() const {
    digraph<T> rev(n_);
    for (auto& e : edges_) {
      rev.add(e.to, e.from, e.cost);
    }
    return rev;
  }
};

template <class T>
class undigraph : public graph<T> {
 public:
  using graph<T>::n_;
  using graph<T>::data_;
  using graph<T>::edges_;

  undigraph(int n) : graph<T>(n) {}

  void add(int from, int to, T cost = 1) {
    int id = edges_.size();
    data_[from].emplace_back(id);
    data_[to].emplace_back(id);
    edges_.push_back({from, to, cost});
  }
};
/*
template <class _Tp>
class SPFA {
 public:
  static constexpr _Tp kInfinity =
      std::numeric_limits<_Tp>::max() / static_cast<_Tp>(2);

  SPFA(int node_size) : node_size_(node_size) { init(); }

  void add(int from, int to, _Tp cost) {
    assert(0 <= from && from < node_size_ && 0 <= to && to < node_size_);
    graph_[from].emplace_back((edge){to, cost});
  }

  // use after solve()
  bool find_negative_cycle() const noexcept { return distance_.empty(); }

  void solve(int source) {
    assert(0 <= source && source < node_size_);
    std::queue<int> que;
    que.emplace(source);
    pending_[source] = true;
    ++times_[source];
    distance_[source] = 0;
    while (!que.empty()) {
      int cur = que.front();
      que.pop();
      pending_[cur] = false;
      for (const auto& next : graph_[cur]) {
        _Tp next_cost = distance_[cur] + next.cost;
        if (next_cost >= distance_[next.to]) continue;
        distance_[next.to] = next_cost;
        if (!pending_[next.to]) {
          if (++times_[next.to] >= node_size_) {
            distance_.clear();
            return;
          }
          pending_[next.to] = true;
          que.emplace(next.to);
        }
      }
    }
    return;
  }

  _Tp operator[](int to) const {
    assert(0 <= to && to < node_size_);
    return distance_[to];
  }

 private:
  struct edge {
    int to;
    _Tp cost;
  };
  int node_size_;
  std::vector<std::vector<edge>> graph_;
  std::vector<_Tp> distance_;
  std::vector<int> pending_;
  std::vector<int> times_;

  void init() {
    graph_.resize(node_size_);
    distance_.assign(node_size_,
                     std::numeric_limits<_Tp>::max() / static_cast<_Tp>(2));
    pending_.assign(node_size_, 0);
    times_.assign(node_size_, 0);
  }
};
*/
template <class T>
vector<T> spfa(const graph<T>& g, int s) {
  assert(0 <= s && s < g.n_);
  vector<T> dist(g.n_, numeric_limits<T>::max());
  vector<int> pend(g.n_, 0);
  vector<int> times(g.n_, 0);

  queue<int> que;
  que.emplace(s);
  pend[s] = true;
  ++times[s];
  dist[s] = 0;
  while (!que.empty()) {
    int cur = que.front(); que.pop();
    pend[cur] = false;
    for (int id : g.data_[cur]) {
      auto& e = g.edges_[id];
      int nxt = e.from ^ e.to ^ cur;
      T ncost = dist[cur] + e.cost;
      if (ncost >= dist[nxt]) continue;
      dist[nxt] = ncost;
      if (!pend[nxt]) {
        if (++times[nxt] >= g.n_) {
          return {};
        }
        pend[nxt] = true;
        que.emplace(nxt);
      }
    }
  }
  return dist;
}

void GRL_1_B() {
  int n, m, r; cin >> n >> m >> r;
  digraph<int> g(n);
  for (int i = 0; i < m; ++i) {
    int s, t, d; cin >> s >> t >> d;
    g.add(s, t, d);
  }
  vector<int> dist = spfa(g, r);
  constexpr int kInfinity = numeric_limits<int>::max();
  if (dist.empty()){
    cout << "NEGATIVE CYCLE" << '\n';
  } else {
    for (int e : dist) {
      if (e == kInfinity) {
        cout << "INF" << '\n';
      } else {
        cout << e << '\n';
      }
    }
  }
}

int main() {
  GRL_1_B();
}


Measured memory_bytes: 3188