AT_abc073_d.[ABC073D] joisino's travel

Atcoder 国有 $N$ 个城镇，通过 $M$ 条双向道路相连。

第 $i$ 条道路连接城镇 $A_i$ 和城镇 $B_i$，距离为 $C_i$。

joisino 姐姐计划访问该国的 $R$ 个城镇 $r_1, r_2, \ldots, r_R$。

前往第一个要访问的城镇以及离开最后一个访问的城镇时可以乘坐飞机，但在访问这些城镇的过程中，必须使用道路进行移动。

请你计算，在合理安排访问这些城镇的顺序，使得通过道路移动的总距离最小的情况下，这个最小的移动距离是多少。

输入通过标准输入按以下格式给出。

$N$ $M$ $R$
$r_1$ $r_2$ $\ldots$ $r_R$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$

请输出合理安排访问顺序后，通过道路移动的最小总距离。

限制条件

• $2 \leq N \leq 200$
• $1 \leq M \leq N \times (N-1)/2$
• $2 \leq R \leq \min(8, N)$（$\min(8, N)$ 表示 $8$ 和 $N$ 中较小的那个）
• $r_i \neq r_j\ (i \neq j)$
• $1 \leq A_i, B_i \leq N,\ A_i \neq B_i$
• $(A_i, B_i) \neq (A_j, B_j),\ (A_i, B_i) \neq (B_j, A_j)\ (i \neq j)$
• $1 \leq C_i \leq 100000$
• 任意两个城镇之间都可以仅通过道路互相到达。
• 所有输入均为整数。

样例解释 1

例如，按照城镇 $1$、城镇 $2$、城镇 $3$ 的顺序访问时，总移动距离为 $2$，这是最小值。

样例解释 2

无论是先访问城镇 $1$ 再访问城镇 $3$，还是先访问城镇 $3$ 再访问城镇 $1$，城镇 $1$ 和城镇 $3$ 之间的最短距离都是 $4$，因此无论选择哪种顺序，答案都是 $4$。

由 ChatGPT 4.1 翻译