【题目描述】

王国有 $n$ 个城市和 $m$ 条带长度的双向道路。请输出任意两个城市之间的最短距离。

如果两个城市无法互相到达，对应位置输出 -1。

【输入格式】

$n$   $m$

$u_1$   $v_1$   $w_1$

$\vdots$

【输出格式】

输出 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个数表示城市 $i$ 到城市 $j$ 的最短距离。

【样例】

4 4
1 2 3
2 3 4
1 3 10
3 4 2

0 3 7 9
3 0 4 6
7 4 0 2
9 6 2 0

【数据范围】

• $1\le n\le400$
• $0\le m\le100000$
• $0\le w_i\le10^9$
• 可能有重边，无自环