408695: GYM103264 D День города

Город Н широко известен своей системой дорог: в городе есть $$$n$$$ перекрёстков и $$$m$$$ широких асфальтированных дорог, каждая из которых соединяет два перекрёстка. Пару десятков лет назад для решения проблем с пробками все дороги сделали платными: проезд по $$$i$$$-й дороге в любую сторону стоит $$$c_i$$$ монет. Пробки с тех пор никуда не исчезли, а цены так и остались.

К очередному дню города мэр города Н решил в качестве подарка жителям выбрать перекрёсток и сделать бесплатными все дороги, соединяющие его с другими перекрёстками. Однако не всё так просто. Дело в том, что каждый день мэр ездит из своего дома на $$$1$$$-м перекрёстке в мэрию на $$$n$$$-м перекрёстке, а проезд стоит денег. Поэтому мэр хочет выбрать перекрёсток и сделать соседние с ним дороги бесплатными так, чтобы в результате самый дешёвый путь из дома в мэрию стал как можно дешевле.

В первой строке входных данных даны два целых числа $$$n\ (2 \le n \le 4\cdot10^5)$$$ и $$$m\ (1 \le m \le 4\cdot10^5)$$$  — число перекрёстков и дорог соответственно.

В каждой из следующих $$$m$$$ строк идут три целых числа $$$v,\ u,\ c\ (1 \le v, u \le n,\ 1 \le c \le 10^9)$$$  — номера перекрёстков, соединяемых $$$i$$$-й дорогой, и стоимость проезда по $$$i$$$-й дороге. Гарантируется, что никакие две дороги не соединяют одну и ту же пару перекрёстков, и ни одна дорога не соединяет какой-либо перекрёсток с ним же.

Гарантируется, что по дорогам можно проехать от перекрёстка $$$1$$$ до перекрёстка $$$n$$$.

Выведите одно целое число  — минимальную стоимость проезда от перекрёстка $$$1$$$ до перекрёстка $$$n$$$ при оптимальном выборе перекрёстка, смежные с которым дороги будут бесплатны.

В тестах общей стоимостью не менее 40 баллов будет выполняться условие $$$n, m \leq 1000$$$.

3 2
1 2 1
2 3 2

0

5 5
1 2 3
1 3 4
2 3 1
3 4 5
4 5 6

4

В первом примере оптимально обнулить дороги, смежные с перекрёстком 2.

Во втором примере оптимально обнулить дороги, смежные с перекрёстком 4.