题目描述
给出一个有向图,包含n个顶点(n<=100),和m条边(m<=10000),图中顶点编号为1到n,边权值均为不超过1000的正整数,求这个图中任意两点间的最短路长度
输入描述
输入的第一行为两个正整数,代表题目描述中的n,m
接下来m行,每行3个正整数x,y,z,表示图中存在一条x指向y,权值为z的边
输出描述
输出n行,每行n个正整数,每个正整数后跟一个空格,第i行第j个正整数代表顶点i到顶点j的最短路长度,如果不存在最短路则输出-1
样例输入
3 4
1 2 1
2 1 1
1 3 2
2 3 4
样例输出
0 1 2
1 0 3
-1 -1 0
提示