벨만-포드

$1$부터 $N$까지 번호가 붙은 $N$개의 정점과 $M$개의 간선으로 이루어진 방향 그래프가 있다.

시작 정점 $S$로부터 각 정점까지의 최단 거리를 구하라.

단, 시작 정점 $S$에서 도달할 수 있는 음수 사이클이 있다면 NEGATIVE CYCLE을 출력한다.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 시작 정점 $S$가 주어진다. $(1 \leq N \leq 1\,000, 0 \leq M \leq 5\,000, 1 \leq S \leq N)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선을 나타내는 세 정수 $u$, $v$, $w$가 주어진다. $(1 \leq u,v \leq N, u \neq v, -10^9 \leq w \leq 10^9)$

이는 $u$번 정점에서 $v$번 정점으로 가는 가중치가 $w$인 간선이 있다는 뜻이다.

같은 두 정점을 연결하는 방향 간선은 두 번 이상 주어지지 않는다.

시작 정점 $S$에서 도달할 수 있는 음수 사이클이 있다면 NEGATIVE CYCLE을 출력한다.

그렇지 않다면 $1$번 정점부터 $N$번 정점까지 시작 정점 $S$로부터의 최단 거리를 한 줄에 하나씩 출력한다.

시작 정점에서 도달할 수 없는 정점이라면 INF를 출력한다.