题目描述

译自 ROI 2021 Day2 T4. Блогеры-путешественники

杨和塔季扬娜决定成为旅行博主，发布他们在全国各地旅行的视频。

这个国家有 $n$ 个城市，编号从 $1$ 到 $n$。城市 $1$ 是首都。城市之间有 $m$ 条双向道路，每条道路连接两个不同的城市。一个城市对之间可以有多条不同的道路。可以通过这些道路从任何一个城市到达另一个城市。

他们计划从首都出发前往另一个城市，但还没有决定去哪个城市。前往城市 $k$ 的路线将由城市 $s_1, s_2, \ldots, s_q$ 和道路 $r_1, r_2, \ldots, r_{q-1}$ 组成，满足以下条件：

• $s_1 = 1, s_q = k$；
• 道路 $r_i$ 连接城市 $s_i$ 和 $s_{i+1}$；
• 他们不会重复经过同一条道路，因此所有 $r_i$ 都是不同的。可以多次经过同一个城市，包括起点城市 $1$ 和终点城市 $k$。

对于每条道路，杨和塔季扬娜计算了拍摄这条道路的视频时长，道路 $i$ 的视频时长为 $t_i$。

在旅行过程中，每个人会选择一条道路拍摄视频。杨喜欢拍短视频，所以他会选择视频时长最短的道路；塔季扬娜喜欢拍长视频，所以她会选择视频时长最长的道路。

两段视频的总时长为

$$\min\limits_{1 \leq i \leq q - 1} t_{r_i} + \max\limits_{1 \leq i \leq q - 1} t_{r_i} $$

他们计划将视频上传到一个知名平台，短视频更受欢迎，因此他们希望最小化两段视频的总时长。为了选择最终的目的地和旅行路线，他们希望计算从城市 $1$ 到每个城市 $k$ 的所有可能路线中，两段视频的最小总时长。

输入格式

第一行包含两个整数 $n, m$ $(2 \leq n \leq 3\cdot 10^5,1 \leq m \leq 3\cdot 10^5)$，表示城市和道路的数量。

接下来的 $m$ 行描述道路。第 $i$ 行包含三个整数 $u_i, v_i, t_i$ $(1 \leq u_i, v_i \leq n, u_i \neq v_i, 0 \leq t_i \leq 10^9)$，表示连接的城市编号和这条道路的视频时长。

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

输出格式

对于每个 $2 \leq k \leq n$，输出从城市 $1$ 到城市 $k$ 的最小视频总时长。

样例 1

输入

3 3
1 2 2
1 3 1
2 3 1

输出

2
2

在第一个样例中，可能的最优路线：

• $1 \overset{t = 1}{\to} 3 \overset{t = 1}{\to} 2$。视频总时长为 $1 + 1 = 2$。
• $1 \overset{t = 1}{\to} 3$。视频总时长为 $1 + 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

在第二个样例中，可能的最优路线：

• $1 \overset{t = 2}{\to} 2$。视频总时长为 $2 + 2 = 4$。
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3$。视频总时长为 $2 + 3 = 5$。
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5 \overset{t = 4}{\to} 4$。视频总时长为 $2 + 4 = 6$。
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5$。视频总时长为 $2 + 4 = 6$。
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5 \overset{t = 4}{\to} 4 \overset{t = 4}{\to} 6$。视频总时长为 $2 + 4 = 6$。
• $1 \overset{t = 2}{\to} 2 \overset{t = 8}{\to} 1 \overset{t = 6}{\to} 7$。视频总时长为 $2 + 8 = 10$。

样例 3

输入

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

输出

3
2
2

在第三个样例中，可能的最优路线：

• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3 \overset{t = 1}{\to} 4 \overset{t = 3}{\to} 2$。视频总时长为 $0 + 3 = 3$。
• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3$。视频总时长为 $0 + 2 = 2$。
• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3 \overset{t = 1}{\to} 4$。视频总时长为 $0 + 2 = 2$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$n$ 的限制	$m$ 的限制	附加限制	子任务依赖
1	$9$	$n \leq 3\cdot 10^5$	$m \leq 3\cdot 10^5$	$m = n - 1$
2	$17$			所有从城市 $1$ 出发的道路 $t_i = 0$
3	$12$			所有从城市 $1$ 出发的道路 $t_i = 10^9$
4	$9$	$n \leq 10$	$m \leq 10$	每对城市之间最多有一条道路
5	$6$	$n \leq 20$	$m \leq 20$		4
6		$n \leq 2000$	$m \leq 2000$	所有道路满足 $\lvert u_i - v_i\rvert = 1$
7	$9$				0, 4~6
8	$8$	$n \leq 5000$	$m \leq 3\cdot 10^5$		0, 4~7
9	$10$	$n \leq 3\cdot 10^5$		对于所有 $a$，存在连接城市 $a$ 和 $a+1$ 的道路；对于任意一对道路 $i,j$，如果 $\lvert u_i - v_i\rvert = 1$ 且 $\lvert u_j - v_j\rvert > 1$，则 $t_i \le t_j$
10	$14$				0, 1~9