n, m, r = gets.split.map &:to_i
g = Array.new(n) { [] }
m.times do
  s, t, w = gets.split.map(&:to_i)
  g[s] << [t, w]
end
d = Array.new n, Float::INFINITY
d[r] = 0
(n-1).times do
  g.each_with_index do |es, s|
    es.each do |t, w|
      d[t] = [d[t], d[s] + w].min
    end
  end
end
nc = g.each_with_index.any? do |es, s|
  es.any? do |t, w|
    d[s] + w < d[t]
  end
end
if nc
  puts 'NEGATIVE CYCLE'
else
  d.each do |w|
    puts w == Float::INFINITY ? 'INF' : w
  end
end