21552번 - Блогеры-путешественники 서브태스크다국어

Ян и Татьяна решили стать блогерами-путешественниками и публиковать ролики о поездках по городам своей страны.

В стране есть $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$, в котором путешествие заканчивается.

Для каждой дороги Ян и Татьяна посчитали длительность ролика, который получится при съемке путешествия по этой дороге, длительность ролика для дороги с номером $i$ равна $t_i$.

В процессе путешествия каждый из ребят выберет одну из дорог маршрута и снимет ролик, посвящённый этой дороге. При этом Ян любит снимать короткие ролики, поэтому выберет на маршруте дорогу с наименьшим значением $t_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}$.

Ребята планируют выложить ролики на известную платформу, где большей популярностью пользуются короткие ролики, поэтому они хотят минимизировать суммарную длину двух роликов. Чтобы выбрать конечный город и маршрут для путешествия, блогеры хотят для каждого конечного города $k$ подсчитать минимальную по всем возможным маршрутам из города $1$ в город $k$ суммарную длину двух роликов.

В первой строке даны два целых числа $n$, $m$ ($2 \leq n \leq 300\,000$, $1 \leq m \leq 300\,000$) --- количество городов и дорог.

Следующие $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$ выведите минимальную суммарную длину роликов Яна и Татьяны для путешествия, заканчивающегося в городе $k$.

В первом примере возможные оптимальные маршруты:

• $1 \overset{t = 1}{\to} 3 \overset{t = 1}{\to} 2$. Длина роликов в маршруте $1 + 1 = 2$.
• $1 \overset{t = 1}{\to} 3$. Длина роликов в маршруте $1 + 1 = 2$.

Во втором примере возможные оптимальные маршруты:

• $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$.

В третьем примере возможные оптимальные маршруты:

• $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$.