def bellman_ford(start, edges)
  dist = Array.new(V + 1, Float::INFINITY)
  dist[start] = 0

  V.times do |i|
    update = false

    edges.each do |from, to, cost|
      if dist[to] > dist[from] + cost
        dist[to] = dist[from] + cost
        update = true

        dist[to] = -Float::INFINITY if i == V - 1
      end
    end

    break unless update
  end

  dist
end

V, E, r = gets.split.map(&:to_i)

edges = []

E.times do
  edges << gets.split.map(&:to_i)
end

dist = bellman_ford(r, edges)

if dist.any? { |d| d == -Float::INFINITY }
  puts 'NEGATIVE CYCLE'
else
  V.times do |i|
    if dist[i] == Float::INFINITY
      puts 'INF'
    else
      puts dist[i]
    end
  end
end

