AT_abc073_d [ABC073D] joisino's travel

[problemUrl]: https://atcoder.jp/contests/abc073/tasks/abc073_d Atcoder国には $ N $ 個の町があり、$ M $ 本の双方向に移動可能な道で結ばれています。 また、 $ i $ 本目の道は町 $ A_i $ と町 $ B_i $ の間を距離 $ C_i $ で結んでいます。 joisinoお姉ちゃんは、この国の $ R $ 個の町 $ r_1,r_2..r_R $ を訪れることとなりました。 最初に訪れる町までの移動と、最後に訪れる町からの移動は空路で行うが、それ以外は道を使わなければなりません。 町を訪れる順番を、道での移動距離が最小となるように決めた時の移動距離を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ R $ $ r_1 $ $ ... $ $ r_R $ $ A_1 $ $ B_1 $ $ C_1 $ $ : $ $ A_M $ $ B_M $ $ C_M $

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

### 制約 - $ 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 $ - すべての町の間は道のみで移動することができる。 - 入力は全て整数である。 ### Sample Explanation 1 例えば、町 $ 1 $ ,町 $ 2 $ ,町 $ 3 $ の順番で訪れると、移動距離が $ 2 $ となり、最小となります。 ### Sample Explanation 2 町 $ 1 $ を訪れたあとに町 $ 3 $ を訪れても、町 $ 3 $ を訪れたあとに町 $ 1 $ を訪れても、町 $ 1 $ と町 $ 3 $ の間の最短距離は $ 4 $ であるため、どの順番を選んだとしても答えは $ 4 $ となります。