题目背景

翻译自 ROI 2021 D2T4。

Sky 决定成为旅行 up 主，发布在全国各个城市旅行的视频。这个国家有 $n$ 个城市，编号从 $1$ 到 $n$。城市 $1$ 是国家的首都。城市之间有 $m$ 条双向道路，编号从 $1$ 到 $m$，每条道路连接两个不同的城市。同时，同一对城市可以通过多条不同的道路连接。从任何一个城市都能够通过道路到达其他任何一个城市。

Sky 和 Aqua 不能分开，所以 Sky 计划和 Aqua 一起从首都出发前往另一个城市，但目前尚未选择具体是哪个城市。到达城市 $k$ 的旅行路线将由城市 $s_1, s_2,\dots,s_q$ 和道路 $r_1,r_2,\dots,r_{q-1}$ 组成，其中：

• $s_1 = 1,s_q = k$；
• 道路 $r_i$ 连接城市 $s_i$ 和 $s_{i+1}$；
• Sky 和 Aqua 不会两次经过同一条道路，因此所有的 $r_i$ 都是不同的。可以多次经过同一个城市，包括旅行起始城市 $1$ 和旅行结束城市 $k$。

对于每条道路，Sky 都计算了在该道路上进行旅行拍摄的视频时长，第 $i$ 条道路的视频时长为 $t_i$。

在旅行过程中，Sky 和 Aqua 都会选择旅行路线中的其中一条道路并拍摄与该道路相关的视频。Sky 喜欢拍短视频，因此 Sky 会选择 $t_i$ 最小的道路；而 Aqua 喜欢拍长视频，因此 Aqua 会选择 $t_i$ 最大的道路。

两个视频的总时长为 $\min\limits_{1\le i \le q-1}t_{r_{i}} + \max\limits_{1\le i \le q-1}t_{r_{i}}$。

题目描述

Sky 不愿意浪费素材，于是想把两个视频拼到一起，并发布到某知名视频网站上。因为现在短视频更受欢迎，所以 Sky 希望尽量减少两个视频的总时长。为了选择旅行的目的地和路线，需要计算出每个目的地 $k$ 在从城市 $1$ 到城市 $k$ 的所有可能路线中两个视频的最小总时长。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 300000$，$1 \le m \le 300000$），分别表示城市和道路的数量。

接下来的 $m$ 行包含道路的描述。第 $i$ 行包含三个整数 $u_i,v_i,t_i$（$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$0 \le t_i \le 10^9$），分别表示连接该道路的城市编号以及在该道路上拍摄视频的时长。

保证通过现有的道路可以从任何一个城市到达任何其他城市。

输出格式

对于每个 $2 \le k \le n$，输出从城市 $1$ 到城市 $k$ 的旅行中 Sky 和 Aqua 的视频总时长的最小值。

3 3
1 2 2
1 3 1
2 3 1

2
2

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

4
5
6
6
6
10

4 4
1 2 2
3 2 0
2 4 3
4 3 1

3
2
2

提示

数据范围见输入格式。