5083 - 图论:最短路(BellmanFord 模版题)

通过次数

33

提交次数

47

时间限制 : 1 秒
内存限制 : 128 MB

求起点到各点的最短距离

输入

第一行2个整数,点的数量n 边的数量m 第二行到第m+1行表示每条边的起点和终点和权值 注意:1号点为起点

输出

一行n个整数,每个整数表示起点到各点的距离

样例

输入

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

输出

0 2 5 7 11 8 16