题目描述

给定一张 $n$ 个点 $m$ 条边的带权无向图。第 $i$ 条边连接结点 $u_i$ 和 $v_i$，边权为 $w_i$。对于一条 $k$ 条边的路径，其边权分别为 $\{e_1,e_2,...,e_k\}$，定义这条路径的权值为 $\sum_{i=1}^k e_i - \max_{i=1}^k e_i + \min_{i=1}^k e_i$，即路径边权之和减去路径最大边权加上路径最小边权。

请你对 $i\in[2,n]$，求出从 $1$ 到 $i$ 的路径的最小权值，如果无法到达输出 $-1$。

输入格式

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

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

输出格式

一行 $n-1$ 整数，第 $i$ 个整数表示对于结点 $i+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

数据范围

$$\begin{aligned} & \bullet \ 2 \le n \le 10^5\\ & \bullet \ 1 \le m \le 2 \times 10^5\\ & \bullet \ 1 \le u_i,v_i \le n\\ & \bullet \ 1 \le w_i \le 10^9 \\ & \bullet 不含重边和自环 \end{aligned}$$