题目描述

给定一张有 $n$ 个点、$m$ 条边的带权无向连通图，保证没有自环和重边。

对于一条由 $k$ 条边 $e_1,e_2,\dots,e_k$ 组成的路径，定义它的权值为

$$\sum_{i=1}^{k} w_{e_i}-\max_{i=1}^{k}w_{e_i}+\min_{i=1}^{k}w_{e_i},$$

其中 $w_e$ 表示边 $e$ 的边权。

请你求出从 $1$ 号点到每个点 $i$（$2\le i\le n$）的最小路径权值。

输入格式

第一行包含两个整数 $n,m$（$2\le n\le 2\cdot 10^5$，$1\le m\le 2\cdot 10^5$），表示点数和边数。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$（$1\le u_i,v_i\le n$，$u_i\ne v_i$，$1\le w_i\le 10^9$），表示一条连接 $u_i$ 和 $v_i$、边权为 $w_i$ 的无向边。

输出格式

输出 $n-1$ 个整数，第 $i$ 个数表示从 $1$ 号点到 $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

样例解释

样例 1 中，从 $1$ 到 $2$ 直接走边权为 $1$ 的边，路径权值为 $1-1+1=1$；从 $1$ 到 $3$ 走 $1\to2\to3$，边权和为 $3$，最大边为 $2$、最小边为 $1$，权值为 $3-2+1=2$。

样例 2、3 同理，按路径上边权和、最大边、最小边代入公式即可。

数据范围与约定

子任务	分值	限制
$1$	$100$	完整范围

对于 $100\%$ 的数据，$2\le n\le 2\cdot 10^5$，$1\le m\le 2\cdot 10^5$，$1\le w_i\le 10^9$，图连通且没有自环和重边。