Restaurants

Interview

Time limit1sMemory limit128 MB

Summary

Every city connects by weighted roads and some hold restaurants; report the largest distance from any city to its closest restaurant.

Level: Medium4 of 10
Topics: Shortest path, Graph, Heap
Solved: No attempts yet

Problem

Bajdonald has decided to open a chain of restaurants in Byteotia. His wish is that every resident be able to visit one of them at least once a week.

He has already tentatively planned in which cities he will build his restaurants. He worries, however, whether every city can reach any of them within a reasonable time. He would therefore like to learn the greatest distance one must travel to reach the nearest restaurant. If that distance turns out to be too large, he will have to change his plans.

The cities of Byteotia are connected by a network of two-way highways. It is guaranteed that every city can reach every other city, though not always directly. The residents of Byteotia live only in cities.

Write a program that:

reads from standard input the map of the country and the planned restaurant sites,
computes the maximum distance that must be traveled from some city to its nearest restaurant (that is, among all distances between a city and its nearest restaurant, find the largest one),
writes the result to standard output.

Input

The first line contains three integers $n$ , $k$ , and $m$ separated by single spaces ( $1 \le n, k \le 1000$ , $1 \le m \le 30000$ ), denoting respectively the number of cities in Byteotia, the number of planned restaurants, and the number of highways. Cities are numbered from $1$ to $n$ .

Each of the next $k$ lines contains a single integer: the number of a city in which a restaurant is to be built. Each of the following $m$ lines contains three integers $a$ , $b$ , and $d$ separated by single spaces. They describe one highway connecting cities $a$ and $b$ ( $a \ne b$ ), whose length is $d$ km ( $1 \le d \le 1000$ ).

Output

Print a single integer: the maximum distance (in kilometers) between some city and its nearest restaurant.

Examples1

Example 1
Input
```
3 1 3
1
1 2 10
1 3 15
3 2 20
```
Expected output
```
15
```