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
[Zgłoś rozwiązanie] [Moje zgłoszenia]