# coding: utf-8
#
# :u ノードのインデックス
# :k u の出次数
# :v u に隣接する頂点の番号
# :w 隣接する頂点への重み
# :d 距離
# :p 前のノード
#

INF  = Float::INFINITY
#INF  = 10**5
Node = Struct.new(:u, :k, :v, :w, :d, :p)

class Graph
  attr :nodes
  def initialize(n)
    @nodes = Array.new(n){ Node.new }
    @nodes = @nodes.map.with_index do |node,idx|
      node.u = idx
      node.d = INF
      node.p = nil
      node.v = []
      node
    end
  end

  def add_graph_edge(u, v, w)
    #puts "#{u} -> #{v} (#{w})"
    if @nodes[u].v.empty?
      @nodes[u].v = [v]
      @nodes[u].w = {v=>w}
    elsif @nodes[u].v.is_a?(Array)
      @nodes[u].v << v
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    else
      @nodes[u].v = [@nodes[u].v, v]
      @nodes[u].w = {v=>w}.merge(@nodes[u].w)
    end
    @nodes[u].k = if @nodes[u].v.is_a?(Array)
                    @nodes[u].v.length
                  else
                    1
                  end
  end

  def bellman_ford(source=0)
    @nodes[source].d = 0

    for i in 0...@nodes.length
      for uv in @nodes[i].v
        u = @nodes[i].u
        v = @nodes[uv].u
        if @nodes[v].d > @nodes[u].d + @nodes[u].w[v]
          @nodes[v].d = @nodes[u].d + @nodes[u].w[v]
          @nodes[v].p = u
        end
      end
    end
  end

  def has_negative_cycle?()
    for node in @nodes
      for v in node.v
        u = node.u
        if @nodes[u].d + @nodes[u].w[v] < @nodes[v].d
          return true
        end
      end
    end
    false
  end
end


lines = $stdin.read
array = lines.split("\n")

V,E,R = array[0].split(" ").map(&:to_i)
graph = Graph.new(V)

array[1..E].each do |s|
  s,t,d = s.split(" ").map(&:to_i)
  graph.add_graph_edge(s,t,d)
end

graph.bellman_ford(R)

if graph.has_negative_cycle?
  puts "NEGATIVE CYCLE"
else
  graph.each{|n| puts n.d}
end
