Miejskie podchody

W kolejnej edycji gier miejskich, organizatorzy postanowili zrobić psikusa uczestnikom. Po wielu ciekawych konkurencjach nastąpi ta ostatnia, najważniejsza i decydująca o zwycięstwie. Organizatorzy tak dobiorą poprzednie zadania, aby uczestnicy wylądowali w konkretnych miejscach w mieście. Ostatnie zadanie będzie polegało na spotkaniu innego użytkownika. Pierwsza para, która się spotka, wygra całe zawody. Znając plan miasta oraz miejsca, w których znajdą się uczestnicy przed tą konkurencją, a także wiedząc, że każdy z nich porusza się z prędkością do 10km/h, oblicz ile co najmniej minut minie, zanim którychś dwóch uczestników się spotka.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczby całkowite u, n oraz m. Są to, kolejno, liczba uczestników, liczba skrzyżowań w mieście, oraz liczba połączeń między skrzyżowaniami (1 <= u,n,m <= 100000, u >= 2). Kolejnych u wierszy zawiera po jednej liczbie całkowitej - numerze skrzyżowania, w którym znajdzie się jedna z osób. Ostatnich m wierszy zawiera informacje o połączeniach. Każdy zawiera trzy liczby całkowite - numery skrzyżowań, które są ze sobą połączone oraz długość połączenia w kilometrach. Numery skrzyżowań to 1,2,...,n, a długości połączeń wynoszą co najwyżej 5000km, w końcu to małe miasto.

Wyjście

Na standardowe wyjście Twój program powinien wypisać jedną liczbę całkowitą p - minimalną liczbę minut, które miną zanim któraś para się spotka. Możesz założyć, że pewna para może się spotkać.

Przyklad

Dla danych:
2 3 3
1
2
1 2 9
3 2 5
1 3 3

Poprawnym wynikiem jest:
24