全点対間最短経路

重み付き有向グラフ $G = (V, E)$ の全点対間最短経路の距離を列挙してください。

入力

入力は以下の形式で与えられます。

$|V|\; |E|$
$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$ の番号が付けられているものとします。

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

出力

グラフ $G$ が負の閉路（辺の重みの和が負になるような閉路）を持つ場合は NEGATIVE CYCLE と１行に出力してください。それ以外の場合以下の形式で距離を出力してください。

$D_{0,0}\; D_{0,1}\; ...\; D_{0,|V|−1}$
$D_{1,0}\; D_{1,1}\; ...\; D_{1,|V|−1}$
:
$D_{|V|−1,0}\; D_{|V|-1,1}\; ...\; D_{|V|−1,|V|−1}$

出力は $|V|$ 行からなります。$i$ 行目に頂点 $i$ から各頂点 $j\; (j = 0, 1, ...|V|-1)$ への最短経路の距離を出力してください。$i$ から $j$ への経路がない場合は INF と出力してください。距離の間に１つの空白を出力してください。

制約

• $1 \leq |V| \leq 100$
• $0 \leq |E| \leq 9,900$
• $-2 \times 10^7 \leq d_i \leq 2 \times 10^7$
• $G$ に多重辺はない
• $G$ に自己ループはない

入力例 1

4 6
0 1 1
0 2 5
1 2 2
1 3 4
2 3 1
3 2 7

出力例 1

0 1 3 4
INF 0 2 3
INF INF 0 1
INF INF 7 0

入力例 2

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

出力例 2

0 1 -5 -4
INF 0 2 3
INF INF 0 1
INF INF 7 0

入力例 3

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

出力例 3

NEGATIVE CYCLE

Note

      解説      

---