题意

给定一张包含 $n$ 个点 $m$ 条边的无向图，无自环无重边，第 $i$ 条边连接 $u_i,v_i$ 两个节点，长度为 $w_i$。

设一条路径经过的边集为 $E$（多次经过仍会加入边集），则定义这条路径的长度为

$$\sum_{i\in E} w_i-\max_{i\in E} w_i +\min_{i\in E} w_i $$

求编号为 1 的点到其他所有点的最短路径长度。

输入格式

第一行两个数 $n,m$。

接下来 $m$ 行，每行三个数 $u_i,v_i,w_i$ 表示一条边。

输出格式

$n-1$ 行，表示每个点的答案。

5 4
5 3 4
2 1 1
3 2 2
2 4 2

1 2 2 4

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

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