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

求起点到各点的最短距离

输入

第一行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
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题