Problem C
Delivering Goods

Photo by kamyar adl cc by-sa 2.0

The road network consists of one-way streets between junctions. The warehouse and clients are all located at a junction. You know the driving time across each street.

You guarantee extremely fast shipping: the trucks start driving immediately at the start of the day and each client $i$ will receive the package at time $T_ i$ where $T_ i$ is the shortest possible driving time for a truck to go from the warehouse to the location of the client $i$.

What is the minimum number of trucks you have to deploy to ensure this guarantee is met? That is, what is the minimum number of trucks such that it is possible to give each truck a driving route so that every client $i$ is visited by some truck at time $T_ i$. Assume it takes no time to load the trucks with the appropriate goods at the start of the day, and it takes no time to drop goods off at a client once the truck arrives at the client. These goods are small enough that each truck can carry goods for as many clients as necessary.

Input

The input consists of a single test case. The first line of each test case consists of three numbers $N$, $M$, and $C$. Here $N$ denotes the number of junctions in the road network ($2 \leq N \leq 10^3$), $M$ denotes the number of streets ($1 \leq M \leq 10^5$), and $C$ denotes the number of clients ($1 \leq C \leq 300$, $C < N$).

The junctions are numbered $0$ to $N-1$. The warehouse is always at junction $0$. The second line consists of $C$ distinct integers between $1$ and $N-1$ indicating the junctions where the clients reside.

The rest of the input consists of $M$ lines, each containing integers $U,V,W$ where $0 \leq U,V \leq N-1$ and $U \neq V$. This indicates there is a one-way street from $U$ to $V$ with driving time $W$. Each street’s driving time $W$ satisfies $1 \leq W \leq 10^9$. It will always be possible to reach every client from the warehouse.

There will be at most one street from a vertex $U$ to another vertex $V$, but there may be streets from both $U$ to $V$ and from $V$ to $U$.

Output

Output a single integer that is the minimum number of vehicles required to ensure each client $i$ is visited at time $T_ i$ by some vehicle.

Explanations of Sample Inputs

In the first sample, one vehicle can follow the path $(0,1,2)$ and the other can follow $(0,3)$. In the second sample, the only solution is to use paths $(0,1)$, $(0,2)$, and $(0,3)$. In the final sample, one vehicle can follow $(0,1)$, another $(0,4,6)$, and the last one $(0,2,3,5,7)$.

4 5 3
1 2 3
0 1 1
0 3 1
0 2 2
1 2 1
3 2 1

2

4 5 3
1 2 3
0 1 1
0 3 1
0 2 1
1 2 1
3 2 1

3

8 11 5
1 3 4 6 7
0 1 5
0 4 1
0 2 2
0 6 6
2 3 1
2 6 3
3 5 7
4 1 5
5 7 3
6 5 6
4 6 4

3