単一始点最短経路（負の重みをもつ辺を含む）

与えられたグラフ $G = (V, E)$ と始点 $r$ について、単一始点最短経路の重みを求めるプログラムを作成してください。$G$ のノード $r$ を始点とし、$r$ から各ノードについて、最短経路上の辺の重みの総和を出力してください。

入力

$|V| \; |E| \; r$
$s_0 \; t_0 \; d_0$
$s_1 \; t_1 \; d_1$
:
$s_{|E|−1} \; t_{|E|−1} \; d_{|E|−1}$

$|V|$, $|E|$ はそれぞれグラフ $G$の頂点の数と辺の数を示す。グラフ $G$の頂点にはそれぞれ $0, 1, ..., |V|-1$ の番号が付けられている。$r$ は始点の番号である。

$s_i$, $t_i$ はグラフ $G$ の $i$ 番目の辺が結ぶ２つの頂点を表す（有向）。$d_i$ は $i$ 番目の辺の重みである。

出力

$G$ において、$r$ から辿りつける負の閉路（経路上の辺の重みの和が負になるような閉路）が存在する場合は NEGATIVE CYCLE と１行に出力する。

そのような閉路が存在しない場合、各頂点 $0, 1, ..., |V|-1$ について、始点 $r$ からの最短経路上の重みの総和を順番に出力する。ただし、$r$ からの経路が存在しない場合は INF と出力する。

制約

• $1 \leq |V| \leq 1000$
• $0 \leq |E| \leq 2000$
• $-10000 \leq d_i \leq 10000$
• $G$ に平行辺はない
• $G$ に自己ループはない

入力例 1

4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

出力例 1

0
2
-3
-1

入力例 2

4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0

出力例 2

NEGATIVE CYCLE

入力例 3

4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2

出力例 3

INF
0
-5
-3

---