class Node
  attr_accessor :name, :child, :done, :cost
  def initialize(i)
    @name = i
    @child = {}
    @done = false
    @cost = 1.0 / 0.0
  end
end

v, e, r = gets.split.map(&:to_i)

node = Array.new(v){|i| Node.new(i)}
e.times{
  s, t, d = gets.split.map(&:to_i)
  node[s].child[t] = d
}

node[r].cost = 0

(v-1).times{|i|
  v.times{|j|
    node[j].child.each{|t,d|
      if node[t].cost > node[j].cost + d then
        node[t].cost = node[j].cost + d
      end
    }
  }
}

v.times{|j|
  node[j].child.each{|t,d|
    if node[j].cost + d < node[t].cost then
      puts "NEGATIVE CYCLE"
      exit
    end
  }
  node[j].cost = "INF" if node[j].cost == 1.0 / 0.0
}

v.times{|j|
  puts node[j].cost
}