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

通过次数

33

提交次数

47

Time Limit : 1 秒
Memory Limit : 128 MB

求起点到各点的最短距离

Input

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

Output

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

Examples

Input

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

Output

0 2 5 7 11 8 16