URI Online Judge | 2359

Allocating Ambulances

By Lucas Maciel, UFMG BR Brazil

Timelimit: 1

There is many cities in the Kindgom of Syldavia, but not all have hospitals (there is a lot of small towns and villages). Therefore, when someone need an urgent care, the closest hospital sends an ambulance for help (this ambulance runs the minimum path to patient town). The Syldavia's governor is very worried with this situation and want know what is the maximum time that someone in Syldavia need to wait to be rescued, and he ask you to answer that.

Observations

The service time as the time that an ambulance spend inside a city could be neglected.

Input

The input is composed of many test cases. Each test case has two integers: N, M e Q (1 ≤ N ≤ 1000, N-1 ≤ M ≤ (N * (N-1)) ÷ 2, 1 ≤ QN), which means the number of cities in Syldavia, the number of highways that connect cities (two-way) and the number of cities that have an hospital, respectively. The next M lines have three integers: A, B and W (1 ≤ A, BN, 1 ≤ W ≤ 50) representing that one ambulance spend W hours to run a highway that connect the cities A and B. The other Q lines have one integer X (1 ≤ XN), indicating that have one hospital in the town X. There is no highway connecting the same pair of cities. It is guaranteed that one ambulance can leave and get from any city to any city.

Output

For each test case, output one line with an integer that represent the maximum time that any inhabitant of Syldavia need to wait to be rescued for one ambulance.

Input Sample Output Sample

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

5
0