Africa has been hit by an earthquake. There are total N cities in Africa out of which K have been affected by this earthquake. The cities are numbered from 1 to N.
United Nations has decided to establish a relief base in one of these (N - K) non-affected cities. Although the UN has lots of relief packets, but it has a single carrier truck to distribute these packets. The truck starts at the base in the morning and goes to all the K cities one by one. It finally returns to the base again in the evening after distributing relief packets to all the K cities.
Note that the truck may have to visit some non-affected cities also while going from one affected city to some other affected city. There are M bi-directional roads between the cities.
It is guaranteed that all the cities are reachable via some combination of roads. You can also assume that the truck has infinite petrol and it needs not to refill during its trip.
Please help UN to find the best city to establish the relief base so that it minimizes the total distance travelled by the truck in a day.
Input Format
Line 1 : Three space separated integers N, M, and K - number of cities, number of roads, and number of affected cities respectively.
Next K lines contains an integer in each line in the range 1 \cdots N identifying an affected city.
Next M lines : Each line contains three space separated integers u, v (1 \leq u, v \leq N), and l (1 \leq l \leq 1000) indicating the presence of a road between cities u and v.
Constraints
1 \leq N \leq 10000
1 \leq M \leq 50000
1 \leq K < N
1 \leq u,v \leq N
1 \leq l \leq 1000
Output Format
The minimum distance the truck needs to travel in a day if the base is set in an optimal location.
Sample TestCase 1
Input :
6 9 3
3
4
5
1 2 7
1 6 6
2 3 1
2 6 5
3 4 1
3 5 3
4 5 1
4 6 4
5 6 10
Output
6
Explanation
The diagram above corresponds to the sample input.
In the diagram above the yellow vertices shows the earthquake-affected cities, while the blue ones are unaffected. The optimal location is to establish the base in city 2. The edges show the trip of the truck, the green ones show the forward trip of the truck, and the blue ones show its return trip.
The optimal location to build base is city 2. The truck then goes like this : 2->3->4->5->4->3->2. Total distance is 1 + 1 + 1 + 1 + 1 + 1 = 6.
Sample TestCase 2
Input
3 3 1
3
1 2 1
1 3 3
2 3 2
Output
4
Explanation
The base should be built in city 2. The truck’s journey will be 2 -> 3 ->2 giving a total distance of 2 + 2 = 4.
I am not able to figure out how to approach this problem. I thought of using floyd Warshall but it would not give the correct result as the reasons are obvious it gives min distance between the pairs.
Now how should I solve this. Please help