Hotel Booking

A transport company frequently has to deliver goods from one city to another. The company has a special deal with a hotel chain that lets its drivers stay for free in any hotel of the chain. A driver may drive at most 10 hours (600 minutes) per day.

The company wants a route from the starting city to the destination city such that the driver can spend every night in one of the chain's hotels, and such that the driving time from one hotel to the next hotel (or to the destination) never exceeds 10 hours (600 minutes) on any single day. The number of days needed for the delivery should also be minimized.

Equivalently, starting from city 1 and passing through hotels so that every leg takes at most 600 minutes, reach city $n$ while minimizing the number of hotels stayed in (the number of hotels that must be booked). The travel time between two points is the length of the shortest route between them in the road network.

The input consists of several test cases. The first line of each test case contains an integer $n$ ($2 \le n \le 10000$), the number of cities considered when planning the route. Cities are numbered from 1 to $n$; city 1 is the starting city and city $n$ is the destination.

The next line contains an integer $h$ followed by the city numbers $c_1, c_2, \dots, c_h$ where the chain's hotels are located ($0 \le h \le \min(n, 100)$).

The third line contains an integer $m$ ($1 \le m \le 10^5$), the number of roads. Each of the following $m$ lines describes one road with three integers $a, b, t$ ($1 \le a, b \le n$ and $1 \le t \le 600$): the road connects cities $a$ and $b$, and a driver needs $t$ minutes to travel from one end to the other. Every road may be used in either direction.

The input is terminated by a test case with $n = 0$.

For each test case, print a single line with the minimum number of hotels the company has to book for a delivery from city 1 to city $n$. If no route exists in which the driver drives at most 10 hours (600 minutes) per day, print $-1$ instead.