8266번 - Podatek 다국어

Władca królestwa Bajtocji, podążając za ogólnoświatowym trendem, postanowił opodatkować wszystko, co się da. Ostatnio wprowadzoną daniną jest tzw. podatek podróżny, który musi płacić każdy, kto przemieszcza się po kraju.

Każdej bajtockiej drodze przypisana jest pewna stawka podatku. Gdy podczas podróży po Bajtocji przejeżdżamy przez miasto, musimy zapłacić w tamtejszym urzędzie podatek, który obliczany jest jako maksimum ze stawki obowiązującej na drodze, którą wjechaliśmy do miasta, oraz stawki na drodze, którą z miasta wyjedziemy. Płaci się też w początkowym i docelowym mieście na trasie podróży - wtedy, obliczając podatek, bierze się pod uwagę tylko jedną drogę.

Twój przyjaciel Bajtazar wybiera się w podróż z Bajtowa do Bajtawy. Pomóż mu tak zaplanować trasę przejazdu, żeby zapłacił jak najniższy podatek.

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n oraz m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000), oznaczające odpowiednio liczbę miast oraz liczbę dróg w Bajtocji. Miasta są ponumerowane liczbami od 1 do n.

Kolejne m wierszy zawiera opisy dróg: w i-tym z tych wierszy znajdują się trzy liczby całkowite a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ c_i ≤ 1 000 000). Oznaczają one, że miasta a_i i b_i są połączone dwukierunkową drogą, na której obowiązująca stawka podatku wynosi c_i bajtalarów. Pomiędzy dowolną parą miast istnieje co najwyżej jedna droga.

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą - minimalny koszt podróży (w bajtalarach) z Bajtowa (miasta oznaczonego numerem 1) do Bajtawy (miasta oznaczonego numerem n). Możesz założyć, że zawsze istnieje ciąg dróg łączący te miasta.

W powyższym przykładzie optymalna trasa wiedzie przez miasta 1, 3, 2 oraz 4. Kolejno zapłacimy w nich podatek w wysokości 2, max(2, 1) = 2, max(1, 4) = 4 oraz 4, co łącznie daje 12 bajtalarów.