n, m, r = gets.split.map(&:to_i)
g = (0..n-1).map { {} }
m.times do
  i, j, c = gets.split.map(&:to_i)
  g[i][j] = c
end

dist = Hash.new(Float::INFINITY)
dist[r] = 0
(n - 1).times do
  (0..n-1).each do |i|
    g[i].each do |j, c|
      dist[j] = [dist[j], dist[i] + c].min
    end
  end
end

has_negative_cycle = false
catch :exit do
  (0..n-1).each do |i|
    g[i].each do |j, c|
      if dist[i] + c < dist[j]
        has_negative_cycle = true
        throw :exit
      end
    end
  end
end

if has_negative_cycle
  puts 'NEGATIVE CYCLE'
else
  (0..n-1).each do |i|
    puts dist[i] == Float::INFINITY ? 'INF' : dist[i]
  end
end
