5083 - 图论:最短路(BellmanFord 模版题)
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