問題文

「でもね君はそんな弱気だった僕をいつも励ましてくれたんだ」

いっきゅうさんは富山県の秘境から湧き出るという伝説の飲み物スパークリング黒ココア を汲みに,遠路はるばる富山県までやってきました.

富山県にはNN個の地点があり,いっきゅうさんは現在地点11におり,スパークリング黒ココアが湧き出る秘境は地点NNにあることがわかっています.

また,富山県にはMM本の道路があり, ii本目の道路は地点uiu_iviv_iを双方向につないでおり,その長さはlil_iです. 富山県の各地点はいくつかの道路を使って移動することによって全ての地点に行けることがわかっています.

いっきゅうさんはスパークリング黒ココアを汲んで帰りたいと思いましたが, それを入れるための容器を持っていないため,秘境に到達する前に容器を買いたいと考えています. 事前に調べた情報によると,富山県にはKK個の商店があり,jj個目の商店は地点pjp_jにあります.

怠惰ないっきゅうさんはなるべく移動距離を少なくしたいと思っています. そこで,地点11からある商店に移動し容器を買い,その後地点NNに移動しスパークリング黒ココアを汲み, そのあと地点11に帰ってくる移動距離の合計の最小値を求めてください.

制約

  • 3N1053 \leq N \leq 10^5
  • 2M2×1052 \leq M \leq 2 \times 10^5
  • 1ui,viN1 \leq u_i,v_i \leq N
  • 1li1091 \leq l_i \leq 10^9
  • uiviu_i \neq v_i
  • 1KN1 \leq K \leq N
  • 1<p1<p2<<pK<N1 < p_1 < p_2 < \cdots < p_K < N
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます.

NNMM
u1u_1v1v_1l1l_1
u2u_2v2v_2l2l_2
\vdots
uMu_MvMv_MlMl_M
KK
p1p_1p2p_2 \cdots pKp_K

出力

問題の答えを整数で出力せよ.

サンプル

入力1
5 6
1 2 1
1 3 3
1 4 4
2 5 1
3 5 5
4 5 2
2
3 4
出力1
8

移動距離の合計の最小値を達成する移動方法は以下の通りです

  • 地点11から地点44に移動し容器を買います
  • 地点44から地点55に移動しスパークリング黒ココアを汲みます
  • 地点55から地点22に移動します
  • 地点22から地点11に移動します

この時の移動距離の合計は4+2+1+1=84+2+1+1=8です. 条件を満たす移動のうち,これが最小値です

入力2
4 4
1 2 100
2 4 100
1 3 2
1 4 1
1
3
出力2
6

同じ道を何度通っても構いません.

提出


Go (1.21)