Traveling Bloggers

Yan and Tatyana decided to become travel bloggers and post videos about trips around the cities of their country.

The country has $n$ cities numbered from 1 to $n$. City 1 is the capital. The cities are connected by $m$ two-way roads numbered from 1 to $m$, and each road connects two different cities. The same pair of cities may be connected by several roads. From any city, you can reach every other city by road.

The travelers plan to leave the capital for some other city, but they have not chosen which one yet. A route to city $k$ consists of cities $s_1, s_2, \ldots, s_q$ and roads $r_1, r_2, \ldots, r_{q-1}$ such that:

• $s_1 = 1$ and $s_q = k$.
• Road $r_i$ connects cities $s_i$ and $s_{i+1}$.
• They do not drive the same road twice, so all $r_i$ are distinct. The route may pass through the same city several times, including city 1, where the trip starts, and city $k$, where it ends.

For each road $i$, the travelers computed the length of the video filmed along it, denoted $t_i$.

During the trip, each traveler picks one road of the route and films a video about it. Yan likes short videos, so he picks the road with the smallest $t_i$. Tatyana prefers long videos, so she picks the road with the largest $t_i$.

The total length of the two videos is $\min\limits_{1 \leq i \leq q-1} t_{r_i} + \max\limits_{1 \leq i \leq q-1} t_{r_i}$.

The travelers plan to upload to a platform where short videos are more popular, so they want to minimize the total length of the two videos. For each destination city $k$, compute the minimum total length over all routes from city 1 to city $k$.

The first line contains two integers $n$, $m$ ($2 \leq n \leq 300\,000$, $1 \leq m \leq 300\,000$), the number of cities and roads.

Each of the next $m$ lines describes a road. The $i$-th of these lines contains three integers $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$), the numbers of the two cities the road connects and the video length for that road.

It is guaranteed that you can travel from any city to any other city using the given roads, possibly through other cities.

For each $2 \leq k \leq n$, print the minimum total length of the two travelers' videos for a trip that ends in city $k$.

In the first example, the possible optimal routes are:

• $1 \overset{t = 1}{\to} 3 \overset{t = 1}{\to} 2$. The video lengths total $1 + 1 = 2$.
• $1 \overset{t = 1}{\to} 3$. The video lengths total $1 + 1 = 2$.

In the second example, the possible optimal routes are:

• $1 \overset{t = 2}{\to} 2$. The video lengths total $2 + 2 = 4$.
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3$. The video lengths total $2 + 3 = 5$.
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5 \overset{t = 4}{\to} 4$. The video lengths total $2 + 4 = 6$.
• $1 \overset{t = 2}{\to} 2 \overset{t = 3}{\to} 3 \overset{t = 4}{\to} 5$. The video lengths total $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$. The video lengths total $2 + 4 = 6$.
• $1 \overset{t = 2}{\to} 2 \overset{t = 8}{\to} 1 \overset{t = 6}{\to} 7$. The video lengths total $2 + 8 = 10$.

In the third example, the possible optimal routes are:

• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3 \overset{t = 1}{\to} 4 \overset{t = 3}{\to} 2$. The video lengths total $0 + 3 = 3$.
• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3$. The video lengths total $0 + 2 = 2$.
• $1 \overset{t = 2}{\to} 2 \overset{t = 0}{\to} 3 \overset{t = 1}{\to} 4$. The video lengths total $0 + 2 = 2$.