Relay Marathon Optimization

This problem involves determining the optimal relay marathon setup in a country with N cities connected by M bidirectional roads. Each road has a traversal time, and there are no self-loops or multiple roads between the same pair of cities.

There are K special cities with indices given by \(A_1, A_2, \dots, A_K\). In a relay marathon, two teams run sequentially under the following rules:

1. The first team starts at start1 and finishes at finish1.
2. The moment the first team reaches finish1, the second team starts from start2 and runs to finish2.
3. The relay marathon finishes when the second team reaches finish2.

For the relay to be valid, start1, finish1, start2, and finish2 must be four distinct special cities. Let \(D(a,b)\) denote the shortest travel time from city \(a\) to city \(b\). If there is no path, define \(D(a,b)=\infty\).

The total relay time is defined as:

[ D(start1, finish1) + D(start2, finish2) ]

Your task is to select valid special cities as \(start1, finish1, start2, finish2\) so that the total time is minimized. If it is impossible to arrange a valid relay (i.e. one or both legs is unreachable between the chosen special cities), output -1.

inputFormat

The input begins with a line containing three integers N, M, and K (the number of cities, roads, and special cities respectively).

The next line contains K distinct integers A1 A2 ... AK indicating the special cities.

Each of the following M lines contains three integers u v w representing a bidirectional road between cities u and v with travel time w.

outputFormat

Output a single integer: the minimum total relay time \(D(start1,finish1) + D(start2,finish2)\) among all valid configurations. If no valid configuration exists, output -1.

sample

4 4 4
1 2 3 4
1 2 3
2 3 4
3 4 5
1 4 10

8