ベルマンフォード法 (Bellman-Ford algorithm)

let v = 0, e = 0, r = 0
let path = []

process.stdin.resume();
process.stdin.setEncoding("utf-8");

process.stdin.on("data", function (input) {
  let num = 0
  const lines = input.split("\n")
  for (const line of lines) {
    if (line === "") {
      break
    }
    const m = line.split(" ").map(v => parseInt(v))
    if (num === 0) {
      v = m[0]
      e = m[1]
      r = m[2]
    } else {
      path.push(m)
    }
    num++
  }
});

process.stdin.on("end", function () {
  // console.log(v, e, r)
  // console.log(path)
  bellmanFord(v, r, path)
});

/**
 * @param {number} v 
 * @param {number} r 
 * @param {number[][]} path 
 */
function bellmanFord(v, r, path) {
  const inf = Number.MAX_SAFE_INTEGER
  const dist = Array(v).fill(inf)
  dist[r] = 0
  for (let i = 0; i < v; i++) {
    let change = false
    for (const [s, t, d] of path) {
      if (dist[s] === inf) {
        continue
      }
      if (dist[s] + d < dist[t]) {
        if (i + 1 === v) {
          console.log('NEGATIVE CYCLE')
          return
        }
        dist[t] = dist[s] + d
        change = true
      } else {
        continue
      }
    }
    if (!change) {
      break
    }
  }
  for (const d of dist) {
    console.log(d === inf ? 'INF' : d)
  }
}