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