Description

给定n个点，m条有向边

求每个点到1号点的最短距离

Input Format

第一行两个数为n,m，n表示顶点个数，m表示边的条数。 (1 ≤ n, m ≤ 100 )

接下来m行，每一行有三个数t1、t2 和t3，表示顶点t1到顶点t2的路程是t3。请注意这些t1->t2是单向的。

Output Format

输出N个数，分别为每个点到1号点的距离

6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4​

0 1 8 4 13 17​

Source

图论 最短路径