P11095 [ROI 2021] Travel (Day 2)

Translated from [ROI 2021 D2T4](https://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-roi-2021-day2.pdf). Sky decided to become a travel content creator and publish travel videos from cities all over the country. This country has $n$ cities, numbered from $1$ to $n$. City $1$ is the capital. There are $m$ undirected roads between the cities, numbered from $1$ to $m$, and each road connects two different cities. At the same time, the same pair of cities may be connected by multiple different roads. From any city, it is possible to reach any other city by roads. Sky and Aqua cannot be separated, so Sky plans to start from the capital together with Aqua and travel to another city, but has not yet decided which city. A travel route to city $k$ consists of cities $s_1, s_2,\dots,s_q$ and roads $r_1,r_2,\dots,r_{q-1}$, where: - $s_1 = 1,s_q = k$; - road $r_i$ connects cities $s_i$ and $s_{i+1}$; - Sky and Aqua will not pass through the same road twice, so all $r_i$ are distinct. They may pass through the same city multiple times, including the starting city $1$ and the ending city $k$. For each road, Sky computed the video length recorded while traveling on that road. The video length for road $i$ is $t_i$. During the trip, Sky and Aqua will each choose one road on the route and record a video related to that road. Sky likes short videos, so Sky will choose the road with the smallest $t_i$; Aqua likes long videos, so Aqua will choose the road with the largest $t_i$. The total length of the two videos is $\min\limits_{1\le i \le q-1}t_{r_{i}} + \max\limits_{1\le i \le q-1}t_{r_{i}}$. Sky does not want to waste footage, so he wants to stitch the two videos together and publish them on a well-known video website. Since short videos are more popular now, Sky wants to minimize the total length of the two videos as much as possible. To choose the destination and the route, you need to compute, for each destination $k$, among all possible routes from city $1$ to city $k$, the minimum possible total length of the two videos.

The first line contains two integers $n$ and $m$ ($2 \le n \le 300000$，$1 \le m \le 300000$), representing the numbers of cities and roads. The next $m$ lines describe the roads. The $i$-th line contains three integers $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$), representing the indices of the cities connected by this road and the video length recorded on this road. It is guaranteed that, using the existing roads, you can get from any city to any other city.

For each $2 \le k \le n$, output the minimum possible total length of Sky's and Aqua's videos for a trip from city $1$ to city $k$.

Constraints are the same as in the input format. | Subtask | Points | $n\le$ | $m\le$ | Special Properties | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $9$ | $300000$ | $300000$ | $m=n-1$ | | $2$ | $17$ | $300000$ | $300000$ | For all roads $i$ connected to city $1$, $t_i=0$ | | $3$ | $12$ | $300000$ | $300000$ | For all roads $i$ connected to city $1$, $t_i=10^9$ | | $4$ | $9$ | $10$ | $10$ | There is at most one road between each pair of cities | | $5$ | $6$ | $20$ | $20$ | There is at most one road between each pair of cities | | $6$ | $6$ | $2000$ | $2000$ | For all roads $i$, $\lvert u_i-v_i\rvert=1$ | | $7$ | $9$ | $2000$ | $2000$ | | | $8$ | $8$ | $5000$ | $300000$ | | | $9$ | $10$ | $300000$ | $300000$ | For all $a$, there is a road between city $a$ and $a + 1$; for any pair of roads $i$ and $j$, if $\lvert u_i − v_i\rvert = 1$ and $\lvert u_j − v_j\rvert > 1$, then $t_i \le t_j$。 | | $10$ | $14$ | $300000$ | $300000$ | | Translated by ChatGPT 5