Bubu

Limit pamięci: 64 MB

Bubu wyszło z jaskini szukać pikników, jednak zauważyli je strażnicy parku Jellystone. Strażnicy próbują zagrodzić drogę Bubu, które ucieka do jaskini. Strażnik złapie Bubu, jeśli znajdzie się w tym samym czasie na polanie, na której jest Bubu. Strażnik może odpoczywać na polanach.

Wejście

W pierwszej linii znajdują się trzy liczby całkowite , , oznaczające odpowiednio liczbę polan w lesie, liczbę przesiek między tymi polanami oraz liczbę strażników. W następnych liniach znajdują się opisy (dwukierunkowych) przesiek w postaci trzech liczb całkowitych , , gdzie oznaczają numery polan, zaś oznacza czas w sekundach, jaki zajmuje strażnikowi lub Bubu przebycie tej przesieki. W następnych liniach podane są numery polan, na których stoją kolejni strażnicy. W ostatniej linii podany jest numer polany, na której znajduje się Bubu. Jaskinia Bubu jest na polanie 1.

Wyjście

Jeżeli Bubu może dotrzeć do jaskini niezłapany przez strażników, należy wypisać minimalny czas dotarcia Bubu do jaskini, w innym przypadku należy wypisać . Zakładamy, że istnieje ścieżka między jaskinią Bubu a polaną, gdzie się ono znajduje.

Przykład

Dla danych wejściowych:

2 1 0
1 2 1
2

poprawną odpowiedzią jest:

1

Autor zadania: Joachim Jelisiejew.