Podatek
Limit pamięci: 128 MB
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.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz
(), oznaczające odpowiednio liczbę miast oraz liczbę
dróg w Bajtocji. Miasta są ponumerowane liczbami od do .
Kolejne wierszy zawiera opisy dróg: w -tym z tych wierszy znajdują się trzy liczby całkowite
().
Oznaczają one, że miasta i są połączone dwukierunkową drogą, na której
obowiązująca stawka podatku wynosi bajtalarów.
Pomiędzy dowolną parą miast istnieje co najwyżej jedna droga.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą -
minimalny koszt podróży (w bajtalarach) z Bajtowa (miasta oznaczonego numerem )
do Bajtawy (miasta oznaczonego numerem ). Możesz założyć, że zawsze
istnieje ciąg dróg łączący te miasta.
Przykład
Dla danych wejściowych:
4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8
poprawną odpowiedzią jest:
12
Wyjaśnienie do przykładu:
W powyższym przykładzie optymalna trasa wiedzie przez miasta , ,
oraz . Kolejno zapłacimy w nich podatek w wysokości , ,
oraz , co łącznie daje bajtalarów.
Autor zadania: Jakub Łącki (i nie tylko).