CF1473E Minimum Path
题号：NC239205
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个包含 n 个点，m 条带权无向边的图，保证这个图没有自环与重边。点编号为 1 到 n，第 i 条边连接编号为 u_i,v_i 的点，有权值 w_i。

我们规定若一条路径所包含的边边集为 E，那么这条路径的权值为 。

现在你需要求出对于所有整数 i 满足 ，从编号为 1 的点到编号为 i 的点所有路径权值的最小值。

输入描述:

第一行两个整数n,m

接下来m行每行三个整数u_i,v_i,w_i表示一条(u_i,v_i)的边权为w_i的边。

输出描述:

输出n-1个数依次表示答案。
示例1

输入

复制 
5 4
5 3 4
2 1 1
3 2 2
2 4 2

输出

复制 
1 2 2 4
示例2

输入

复制 
6 8
3 1 1
3 6 2
5 4 2
4 2 2
6 1 1
5 2 1
3 2 3
1 5 4

输出

复制 
2 1 4 3 1
示例3

输入

复制 
7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4

输出

复制 
3 4 2 7 7 3

备注: