题目描述

Jan 和 Tatiana 决定成为旅行博主，发布他们在国家各城市旅行的视频。

这个国家有 $n$ 个城市，编号为 $1$ 到 $n$。城市 $1$ 是首都。城市之间有 $m$ 条双向道路，编号为 $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$。

对每条道路，Jan 和 Tatiana 预先估计了沿这条道路拍摄得到的视频长度。第 $i$ 条道路的视频长度为 $t_i$。

在旅行过程中，他们二人各会选择路线中的一条道路拍视频：

• Jan 喜欢短视频，因此选择路线中 $t_i$ 最小的道路；
• Tatiana 喜欢长视频，因此选择路线中 $t_i$ 最大的道路。

两段视频总长度为：

$$\min_{1\le i\le q-1} t_{r_i}+\max_{1\le i\le q-1} t_{r_i}$$

他们想让视频总长度尽量短。请对每个终点城市 $k$，计算从城市 $1$ 到城市 $k$ 的所有合法路线中，上述总长度的最小值。

输入格式

第一行包含两个整数 $n,m$，表示城市数和道路数。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,t_i$，表示第 $i$ 条道路连接城市 $u_i$ 与 $v_i$，该道路的视频长度为 $t_i$。

保证整个图连通。

输出格式

对每个 $k=2,3,\ldots,n$，输出一行，表示以城市 $k$ 为终点时的最小视频总长度。

数据范围

$$2\le n\le 300000, \qquad 1\le m\le 300000$$ $$1\le u_i,v_i\le n, \qquad u_i\ne v_i, \qquad 0\le t_i\le 10^9$$

样例 1 输入

3 3
1 2 2
1 3 1
2 3 1

样例 1 输出

2
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

样例 2 输出

4
5
6
6
6
10

样例 3 输入

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

样例 3 输出

3
2
2

说明

第一个样例中，可以取如下最优路线：

• 到城市 2：$1\xrightarrow{t=1}3\xrightarrow{t=1}2$，视频长度和为 $1+1=2$；
• 到城市 3：$1\xrightarrow{t=1}3$，视频长度和为 $1+1=2$。

第二个样例中可能的最优路线包括：

• 到城市 2：$1\xrightarrow{t=2}2$，长度和为 $2+2=4$；
• 到城市 3：$1\xrightarrow{t=2}2\xrightarrow{t=3}3$，长度和为 $2+3=5$；
• 到城市 4：$1\xrightarrow{t=2}2\xrightarrow{t=3}3\xrightarrow{t=4}5\xrightarrow{t=4}4$，长度和为 $2+4=6$；
• 到城市 5：$1\xrightarrow{t=2}2\xrightarrow{t=3}3\xrightarrow{t=4}5$，长度和为 $2+4=6$；
• 到城市 6：$1\xrightarrow{t=2}2\xrightarrow{t=3}3\xrightarrow{t=4}5\xrightarrow{t=4}4\xrightarrow{t=4}6$，长度和为 $2+4=6$；
• 到城市 7：$1\xrightarrow{t=2}2\xrightarrow{t=8}1\xrightarrow{t=6}7$，长度和为 $2+8=10$。

第三个样例中可能的最优路线包括：

• 到城市 2：$1\xrightarrow{t=2}2\xrightarrow{t=0}3\xrightarrow{t=1}4\xrightarrow{t=3}2$，长度和为 $0+3=3$；
• 到城市 3：$1\xrightarrow{t=2}2\xrightarrow{t=0}3$，长度和为 $0+2=2$；
• 到城市 4：$1\xrightarrow{t=2}2\xrightarrow{t=0}3\xrightarrow{t=1}4$，长度和为 $0+2=2$。

子任务

子任务	分值	限制	附加限制	依赖	检查信息
1	9	$n,m\le 300000$	$m=n-1$	无	第一处错误
2	17		对所有从城市 1 出发的道路 $i$，$t_i=0$
3	12		对所有从城市 1 出发的道路 $i$，$t_i=10^9$
4	9	$n,m\le 10$	任意一对城市之间至多有一条道路
5	6	$n,m\le 20$		4
6		$n,m\le 2000$	对所有道路，$	u_i-v_i	=1$
7	9		无	U, 4-6	第一处错误
8		$n\le 5000,\ m\le 300000$		U, 4-7	只显示分数
9	10	$n,m\le 300000$	对所有 $a$，城市 $a$ 与 $a+1$ 之间存在道路；且对任意两条道路 $i,j$，若 $	u_i-v_i	=1$且$
10	14		无	U, 1-9	只显示分数