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