题目描述

当你知道了dijkstra后，单源最短路仿佛是如此的简单——但迪杰斯塔拉无法解决负权问题 这个时候就要请出Bellman-Ford了 (由于无法正确表述意思，请大家自信搜索或观看啊哈算法详解)

SPFA是超越三幻神的存在，它基于Bellman算法，是它的队列优化改良版，是真正的万金油算法 不过这不代表其它幻神无法使用，他们都有各自的用处 floyd代码简短，是竞赛快刀，使用它过水题可谓切菜一般 dijksra是针对性杀器，对于某些题目下必须用它解

而三幻神也有各自的改良版， dijkstra也有邻接表和优先队列(堆优化)改良版 floyd也可以根据题目要求进行大量剪枝

心中有神，代码便有神，但是别迷信神，要根据战场情况适度使用

输入格式

输入两个整数n和m，中间用空格隔开，代表城市个数和道路条数(1 后面m行,每行输入三个整数a,b,c，中间用空格隔开 表示 a到b的距离为c   ( 1-100 ) 题目保证每次的a b不会重复 注意，这里仅仅指a到b有路，但b到a没有 有多个输入样例

题目保证无负权回路!!!!

输出格式

输出城市1到所有路的最短距离（为1*n的矩阵） 若是自己则输出0 若是无法相通则输出0x3f3f3f3f的10进制表达式 (既int a=0x3f3f3f3f) 中间用空格隔开，每行末尾无空格

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

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

提示

出题人： Extra_Guo 郭程 计算1801