题目描述

《模板》

【模板】Floyd 给出一张由 n 个点 m 条边组成的无向连通图。 求出所有点对 (i,j) 之间的最短路径。

输入格式

第一行为两个整数 n,m，分别代表点的个数和边的条数。 接下来 m 行，每行三个整数 u,v,w，代表 u,v 之间存在一条边权为 w 的边。

输出格式

输出 n 行每行 n 个整数。 第 i 行的第 j 个整数代表从 i 到 j 的最短路径。

样例

输入样例 1

5 7
1 3 4
1 4 6
1 5 8
3 5 1
3 2 7
2 5 2 
4 2 9

输出样例 1

0 7 4 6 5
7 0 3 9 2
4 3 0 10 1
6 9 10 0 11
5 2 1 11 0

输入样例 2

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

输出样例 2

0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0

输入样例 3

4 12
1 2 3
1 3 2
1 4 1
2 1 4
2 3 5
2 4 6
3 1 7
3 2 2
3 4 3
4 1 8
4 2 1
4 3 4

输出样例 3

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

输入样例 4

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

输出样例 4

0 3 4
3 0 1
4 1 0

输入样例 5

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

输出样例 5

0 3 1
3 0 2
1 2 0