No submission language available for this problem.

Background

Special for beginners, ^_^

Description

（题面还需要改）

求出从 1 出发到各点的最短路径。

Format

Input

第一行输入n 和 m，代表 n 个节点，m条边

后面 m 行，每行有 x, y, z，代表 x 到 y 的路距离为 z

注意数据有重边，且若无法到达，设计 inf=1000000000

Output

按顶点编号 2~n 各个顶点到顶点 1 的最短距离，一个数据占一行。

Samples

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

2
2
1
1
1
2
2
3
3

Limitation

1<=n, m<=1000, 1<=u, v<=n, 1<=w<=1000

1s, 1024KiB for each test case.