시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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.

입력

W pierwszej linii znajdują się trzy liczby całkowite n, m, s, (1 ≤ n ≤ 105, 0 ≤ m ≤ 2 · 105, 0 ≤ s ≤ 3 · 104) oznaczające odpowiednio liczbę polan w lesie, liczbę przesiek między tymi polanami oraz liczbę strażników. W następnych m liniach znajdują się opisy (dwukierunkowych) przesiek w postaci trzech liczb całkowitych a, b, w, (1 ≤ a, bn, 1 ≤ w ≤ 109), gdzie a, b oznaczają numery polan, zaś w oznacza czas w sekundach, jaki zajmuje strażnikowi lub Bubu przebycie tej przesieki. W następnych s 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.

출력

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ć -1. Zakładamy, że istnieje ścieżka między jaskinią Bubu a polaną, gdzie się ono znajduje.

예제 입력 1

2 1 0
1 2 1
2

예제 출력 1

1