Minimum Total Communication Distance

In this problem, you are given a network of N cities and M bidirectional roads. Among these cities, there are P distribution centers. Each road connects two cities and has an associated length. Two distribution centers can communicate if there is a path between them (possibly through other cities).

Your task is to compute the minimum total distance required to ensure that all distribution centers are connected, i.e. there is a communication path between every pair of distribution centers. To achieve this, you first need to compute the shortest distance between every pair of cities. Let \(d(i,j)\) denote the shortest distance between city \(i\) and city \(j\). Then, consider a complete graph on the distribution centers where the weight between two centers \(i\) and \(j\) is \(d(i,j)\). Find a Minimum Spanning Tree (MST) of this graph—the sum of the weights in the MST is the answer.

You may use the Floyd–Warshall algorithm to compute all pairs shortest paths and then use Prim's (or Kruskal's) algorithm to find the MST.

inputFormat

The input is given via standard input (stdin) in the following format:

N M P
D1 D2 ... DP
u1 v1 w1
u2 v2 w2
...
uM vM wM

Where:

• N is the number of cities.
• M is the number of roads.
• P is the number of distribution centers.
• The second line contains P integers denoting the indices of the distribution centers.
• Each of the next M lines contains three integers \(u, v, w\) indicating that there is a bidirectional road between cities \(u\) and \(v\) with length \(w\).

outputFormat

Output a single integer to standard output (stdout) which is the minimum total distance required for connectivity among all distribution centers.

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

6