题目描述

在Atcoder州里有 $N$ 个城镇，由 $M$ 条双向道路连接。

第 $i$ 条道路连接了城镇 $A_i$ 和 $B_i$，长度为 $C_i$。

Joisino 正在此州访问 $R$ 个城镇，分别为 $r_1,r_2,..,r_R$（不一定按顺序）。

她将飞往第一个访问的城镇，并从最后一个访问的城镇返回，但在剩下的旅程中她必须通过道路旅行。

如果她按照最小化道路行驶距离的顺序访问城镇，那么行驶距离是多少？

约束条件

• $2≤N≤200$
• $1≤M≤N×(N-1)/2$
• $2≤R≤min(8,N)$ （$min(8,N)$ 是 $8$ 和 $N$ 中较小的一个。）
• $r_i≠r_j (i≠j)$
• $1≤A_i,B_i≤N, A_i≠B_i$
• $(A_i,B_i)≠(A_j,B_j),(A_i,B_i)≠(B_j,A_j) (i≠j)$
• $1≤C_i≤100000$
• 每个城镇都可以通过道路互相到达。
• 所有输入值均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $R$ $r_1$ $...$ $r_R$ $A_1$ $B_1$ $C_1$ $:$ $A_M$ $B_M$ $C_M$

输出

如果Joisino按照最小化行驶距离的顺序访问城镇，则输出所行驶的道路距离。

示例输入 1

3 3 3
1 2 3
1 2 1
2 3 1
3 1 4

示例输出 1

2

例如，如果她按照 $1$、$2$、$3$ 的顺序访问城镇，行驶距离将为 $2$，这是可能的最小距离。

示例输入 2

3 3 2
1 3
2 3 2
1 3 6
1 2 2

示例输出 2

4

城镇 $1$ 和城镇 $3$ 之间的最短距离为 $4$。因此，无论她先访问城镇 $1$ 还是城镇 $3$，行驶距离都将为 $4$。

示例输入 3

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

示例输出 3

3