6472: 【模板】Floyd

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:9 Solved:2

Description

给出一张由  个点  条边组成的无向图。

求出所有点对 (,) 之间的最短路径。

Input

第一行为两个整数 ,,分别代表点的个数和边的条数。

接下来  行,每行三个整数 ,,,代表 , 之间存在一条边权为  的边。

Output

输出  行每行  个整数。

第  行的第  个整数代表从  到  的最短路径。

如果两点间不存在路径,输出-1

Sample Input Copy

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

Sample Output Copy

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

HINT

对于 100% 的数据,1004500,任意一条边的权值  是正整数且 11000

数据中可能存在重边。