Farmer John's Optimal Farm Relocation

Farmer John is moving to minimize his daily travel distance. The region consists of N towns and M bi‐directional roads connecting them, and it is possible to travel between any pair of towns. There are K towns with markets that Farmer John visits every day. He wants to build his new farm in one of the towns without a market, so that when he leaves his farm, visits all K market towns (in any order) and returns home, his total travel distance is minimized.

Formally, for a candidate town i (which does not have a market) and a permutation \(\pi\) of the K market towns, the total distance of the journey is:

[ d(i,\pi(1)) + \sum_{j=1}^{K-1} d(\pi(j), \pi(j+1)) + d(\pi(K), i), ]

where \(d(u,v)\) is the length of the shortest path between towns \(u\) and \(v\). Your task is to compute the minimum possible travel distance if Farmer John builds his farm at an optimal town and chooses the best order of visiting the markets.

inputFormat

The input begins with a line containing three integers N (1 \le N \le 10,000), M (1 \le M \le 50,000), and K (1 \le K \le 5). The second line contains K distinct integers representing the towns that have markets. Each of the next M lines contains three integers u v w, indicating that there is a bi-directional road between town u and town v with length w (a positive integer).

outputFormat

Output a single integer representing the minimum total travel distance for Farmer John's daily route if he builds his farm at the optimal town.

sample

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

10