AT_codequeen2025_final_g 全国ツアー

日本には $ 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 $ に到達するまでに必要な移動距離の最小値を求めてください。 ただし、移動の途中で同じ都市を複数回通っても構いません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_K $ $ U_1 $ $ V_1 $ $ C_1 $ $ U_2 $ $ V_2 $ $ C_2 $ $ \vdots $ $ U_M $ $ V_M $ $ C_M $

答えをキロメートル単位で出力せよ。ただし、単位は出力せず、答えを整数で出力せよ。

### Sample Explanation 1 以下のように移動することで $ 4 $ つの都市でライブをすることができます： - 都市 $ 1 $ でライブをする。 - 都市 $ 1 $ から都市 $ 3 $ に $ 1 $ キロメートル移動する。 - 都市 $ 3 $ から都市 $ 2 $ に $ 10 $ キロメートル移動する。 - 都市 $ 2 $ でライブをする。 - 都市 $ 2 $ から都市 $ 3 $ に $ 10 $ キロメートル移動する。 - 都市 $ 3 $ から都市 $ 4 $ に $ 100 $ キロメートル移動する。 - 都市 $ 4 $ でライブをする。 - 都市 $ 4 $ から都市 $ 5 $ に $ 1000 $ キロメートル移動する。 - 都市 $ 5 $ でライブをする。 この場合の移動距離は $ 1121 $ キロメートルです。 移動距離が $ 1121 $ キロメートル未満となるように移動することはできないので、 $ 1121 $ を出力してください。 ### Constraints - $ 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 $ - 入力される値は全て整数