#1033. 「USACO 2012.2 Silver」Relocation

FJ决定搬家，重新建设农场，以便最小化他每天的行程。

FJ搬往的区域有N(1 <= N <= 10,000)个城镇，共有M (1 <= M <= 50,000)条双向道路连接某些城镇，所有城镇都能找到互通路线。

有K (1 <= K <= 5)个城镇建有市场，FJ每天离开新农场后，都要光顾这K个城镇，并返回农场。FJ希望建设农场的城镇不包含市场。

请帮助FJ选择最佳城镇建设农场，使得他每天的行程最小。

* Line 1: Three space-separated integers, N, M, and K.

* Lines 2..1+K: Line i+1 contains an integer in the range 1...N identifying the town containing the ith market. Each market is in a different town.

* Lines 2+K..1+K+M: Each line contains 3 space-separated integers, i, j (1 <= i,j <= N), and L (1 <= L <= 1000), indicating the presence of a road of length L from town i to town j.

* Line 1: The minimum distance FJ needs to travel during his daily routine, if he builds his farm in an optimal location.

输入 #1

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

输出 #1

12

There are 5 towns, with towns 1, 2, and 3 having markets. There are 6 roads.

FJ builds his farm in town 5. His daily schedule takes him through towns 5-1-2-3-2-1-5, for a total distance of 12.