问题描述

给出一张无向图，请输出一个矩阵，其中第 $i$ 行第 $j$ 列表示点 $i$ 到点 $j$ 的最短距路径。

输入格式

第 $1$ 行包含两个整数 $n$,$m$，分别表示点的个数、无向边的个数。

接下来 $m$ 行每行包含三个整数 $F_i$,$G_i$,$W_i$，分别表示第 $i$ 条无向边的两个点和长度。

数据范围

$n \le 200$, $m \le 10000$

$1 \le F_i,G_i \le n$

$0 \lt W_i \le 100$

输出格式

输出一个矩阵，其中第 $i$ 行第 $j$ 列表示点 $i$ 到点 $j$ 的最短距路径，若两点之间无法到达则输出 $-1$ 。

样例

4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

0 2 4 3
2 0 2 1
4 2 0 3
3 1 3 0