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.

Input Format

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $ n $ oraz $ m $ ($2 \le n \le 100\,000$, $1 \le m \le 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 \le a_{i}, b_{i} \le n$, $ a_{i} \ne b_{i} $, $1 \le c_{i} \le 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.

Output Format

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.

Example

Input

4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8

Output

12

Notes

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.