P3044 [USACO12FEB] Relocation S

Farmer John 决定搬家，重新建设农场，以便最小化他每天的行程。 Farmer John 搬往的区域有 $N$（$1 \le N \le 10\,000$）个城镇，共有 $M$（$1 \le M \le 50\,000$）条双向道路连接某些城镇，所有城镇都能找到互通路线。 有 $K$（$1 \le K \le 5$）个城镇建有市场，Farmer John 每天离开新农场后，都要光顾这 $K$ 个城镇，并返回农场。Farmer John 希望建设农场的城镇不包含市场。 请帮助 Farmer John 计算选择最佳城镇建设农场时，他每天行程长度的最小可能值。

从标准输入读入数据。 第一行包含三个整数 $N, M, K$。 接下来 $K$ 行每行包含一个在范围 $1 \sim N$ 中的整数，表示市场的编号。每个市场都在不同的城镇。 接下来 $M$ 行每行包含三个整数 $i, j, L$（$1 \le i, j \le N$，$1 \le L \le 1000$），表示有从城镇 $i$ 到城镇 $j$ 的长度为 $L$ 的双向道路。

输出到标准输出。 一行一个整数，表示 Farmer John 在选择最佳城镇建设农场时，他每天行程长度的最小可能值。

在这组样例中，有 $5$ 座城镇，城镇 $1, 2, 3$ 有市场，还有 $6$ 条双向道路。 一种可能的最优方案：FJ 在城镇 $5$ 建设农场。他每天的行程为 $5 \to 1 \to 2 \to 3 \to 2 \to 1 \to 5$，总距离为 $12$。