問題文

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$

出力

町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を出力せよ。

入力例 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$ を訪れても、町 $3$ を訪れたあとに町 $1$ を訪れても、町 $1$ と町 $3$ の間の最短距離は $4$ であるため、どの順番を選んだとしても答えは $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