P11095 [ROI 2021] 旅行 (Day 2)

翻译自 [ROI 2021 D2T4](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf)。 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 的视频总时长的最小值。

数据范围见输入格式。 | 子任务 | 分值 | $n\le$ | $m\le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $9$ | $300000$ | $300000$ | $m=n-1$ | | $2$ | $17$ | $300000$ | $300000$ | 所有连接到城市 $1$ 的道路 $i$ 满足 $t_i=0$ | | $3$ | $12$ | $300000$ | $300000$ | 所有连接到城市 $1$ 的道路 $i$ 满足 $t_i=10^9$ | | $4$ | $9$ | $10$ | $10$ | 每对城市的连接不超过一条道路 | | $5$ | $6$ | $20$ | $20$ | 每对城市的连接不超过一条道路 | | $6$ | $6$ | $2000$ | $2000$ | 对于所有道路 $i$，$\lvert u_i-v_i\rvert=1$ | | $7$ | $9$ | $2000$ | $2000$ | | | $8$ | $8$ | $5000$ | $300000$ | | | $9$ | $10$ | $300000$ | $300000$ | 对于所有的 $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$ | $300000$ | $300000$ | |