Задача №114294. День города
Город Н широко известен своей системой дорог: в городе есть \(\)\(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\)\(\).
В первом примере оптимально обнулить дороги, смежные с перекрёстком 2.
Во втором примере оптимально обнулить дороги, смежные с перекрёстком 4.
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