Блогеры-путешественники

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

В стране есть $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$.