問題文

日本には N 箇所の都市があり、都市同士を双方向に結ぶ M 本の道路が存在します。都市には都市 1 から都市 N までの番号がついており、 i 本目の道路は都市 U_i と都市 V_i を結ぶ、長さ C_i キロメートルの道路です。道路を通る方法以外で都市間の移動はできません。

また、 N 箇所の都市のうち K 箇所にライブ会場があります。具体的には、 k=1,2,\ldots,K に対し都市 A_k にライブ会場があります。ここで、K は 4 以上であることと都市 1 と都市 N には必ずライブ会場があることが保証されます。

人気アイドルグループである Bit♡Beat は全国ツアーを開催することにしました。

全国ツアーは異なる 4 つの都市のライブ会場で行います。また、最初のライブは都市 1 で、最後のライブは都市 N で行う必要があります。

都市 1 からスタートして 4 つの都市（都市 1,N 含む）でライブを行い都市 N に到達するまでに必要な移動距離の最小値を求めてください。

ただし、移動の途中で同じ都市を複数回通っても構いません。

制約

• 4\le N\le 10^5
• \displaystyle N-1 \le M\le \min\left(2\times 10^5, \frac{N(N-1)}2 \right)
• 1\le U_i < V_i \le N
• 1\le C_i \le 10^9
• 与えられるグラフは単純で連結
• 4\le K\le N
• 1 = A_1 < A_2 < \ldots < A_K = N
• 入力される値は全て整数

入力例 1

5 4 4
1 2 4 5
1 3 1
2 3 10
3 4 100
4 5 1000

出力例 1

1121

以下のように移動することで 4 つの都市でライブをすることができます：

• 都市 1 でライブをする。
• 都市 1 から都市 3 に 1 キロメートル移動する。
• 都市 3 から都市 2 に 10 キロメートル移動する。
• 都市 2 でライブをする。
• 都市 2 から都市 3 に 10 キロメートル移動する。
• 都市 3 から都市 4 に 100 キロメートル移動する。
• 都市 4 でライブをする。
• 都市 4 から都市 5 に 1000 キロメートル移動する。
• 都市 5 でライブをする。

この場合の移動距離は 1121 キロメートルです。

移動距離が 1121 キロメートル未満となるように移動することはできないので、 1121 を出力してください。

入力例 2

6 11 4
1 4 5 6
1 2 40
2 3 30
3 6 20
1 4 100
2 4 80
3 4 60
4 6 40
1 5 80
2 5 70
3 5 60
5 6 50

出力例 2

210

入力例 3

15 22 5
1 5 11 13 15
1 2 668
1 6 869
2 3 633
2 7 563
3 4 32
3 8 158
4 5 314
4 9 859
5 10 935
6 7 826
6 11 167
7 8 112
7 12 606
8 9 279
8 13 731
9 10 181
9 14 442
10 15 557
11 12 499
12 13 174
13 14 791
14 15 477

出力例 3

2977