호텔 예약

한 운송 회사는 종종 물건을 한 도시에서 다른 도시로 배달해야 한다. 이 회사는 어떤 호텔 체인과 특별 계약을 맺어, 소속 운전기사들이 그 체인의 호텔에서 무료로 묵을 수 있다. 운전기사는 하루에 최대 10시간(즉 600분)까지만 운전할 수 있다.

운송 회사는 출발 도시에서 도착 도시까지 가는 경로를 찾되, 운전기사가 매일 밤 그 체인의 호텔 중 한 곳에서 잘 수 있어야 하고, 한 호텔에서 다음 호텔(또는 도착 도시)까지 하루 운전 시간이 10시간(600분)을 넘지 않아야 한다. 물론 배달에 필요한 날짜 수도 최소가 되어야 한다.

즉, 출발 도시 1에서 시작하여 각 구간이 600분 이하가 되도록 호텔들을 거쳐 도착 도시 $n$에 이르는 경로 중, 중간에 묵는 호텔의 수(예약해야 하는 호텔 수)가 최소가 되도록 하라. 두 지점 사이의 이동 시간은 도로망에서 두 지점을 잇는 최단 경로의 소요 시간으로 계산한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 경로 계획에서 고려할 도시의 수를 나타내는 정수 $n$ ($2 \le n \le 10000$)이 주어진다. 편의상 도시는 1번부터 $n$번까지 번호가 매겨지며, 1번이 출발 도시, $n$번이 도착 도시다.

다음 줄에는 정수 $h$와 그 뒤로 호텔 체인의 호텔이 위치한 도시 번호 $c_1, c_2, \dots, c_h$가 주어진다 ($0 \le h \le \min(n, 100)$).

그 다음 줄에는 고려할 도로의 수를 나타내는 정수 $m$ ($1 \le m \le 10^5$)이 주어진다. 이어지는 $m$개의 줄에는 각 도로가 하나씩 주어지며, 각 줄에는 세 정수 $a, b, t$ ($1 \le a, b \le n$, $1 \le t \le 600$)가 있다. 이는 도시 $a$와 $b$를 잇는 도로를 뜻하며, 운전기사가 그 도로의 한 끝에서 다른 끝까지 이동하는 데 $t$분이 걸린다. 모든 도로는 양방향으로 통행할 수 있다.

$n = 0$인 테스트 케이스로 전체 입력이 끝난다.

각 테스트 케이스마다, 도시 1에서 도시 $n$까지 배달하기 위해 운송 회사가 예약해야 하는 호텔의 최소 개수를 한 줄에 출력한다. 하루 운전 시간이 10시간(600분)을 넘지 않는 경로를 찾는 것이 불가능하면 대신 $-1$을 출력한다.