Zadanie: Restauracje

Limit pamięci: 32 MB

Bajdonald postanowił uruchomić w Bajtocji sieć restauracji. Jego pragnieniem jest, żeby każdy mieszkaniec mógł choćby raz w tygodniu wybrać się do jednej z nich.

Wstępnie zaplanował już, w których miastach postawi swoje restauracje. Obawia się jednak, czy z każdego miasta będzie można w rozsądnym czasie dojechać do jakiejkolwiek z nich. Chciałby więc dowiedzieć się, jaką największą odległość trzeba pokonać, żeby dostać się do najbliższej restauracji. Jeśli ta odległość okaże się zbyt duża, będzie musiał zmienić swoje plany.

Miasta w Bajtocji są połączone siecią dwukierunkowych autostrad. Wiadomo, że z każdego miasta można dojechać do każdego innego, choć nie zawsze bezpośrednio. Mieszkańcy Bajtocji żyją tylko w miastach.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia mapę kraju oraz planowane miejsca budowy restauracji,
• wyznaczy maksymalną odległość jaką należy pokonać z pewnego miasta do najbliższej restauracji (to znaczy, spośród wszystkich odległości pomiędzy miastami a najbliższymi restauracjami, należy znaleźć tę największą),
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , i , , , oddzielone pojedynczymi odstępami, określające odpowiednio - liczbę miast w Bajtocji, liczbę planowanych restauracji oraz liczbę autostrad. Miasta są ponumerowane od do .

W każdym z kolejnych wierszy znajduje się jedna liczba - numer miasta, w którym ma być zbudowana restauracja. W każdym z następnych wierszy znajdują się trzy liczby całkowite , i , oddzielone pojedynczymi odstępami. Liczby te opisują jedną autostradę - autostrada łączy miasta i (), a jej długość wynosi km, .

Wyjście

W jedynym wierszu standardowego wyjścia powinna zostać zapisana jedna liczba całkowita, równa maksymalnej odlegości (w kilometrach) pomiędzy pewnym miastem, a najbliżej położoną restauracją.

Przykład

Dla danych wejściowych:

3 1 3
1
1 2 10
1 3 15
3 2 20

poprawną odpowiedzią jest:

15