問題文

N の地点と M 個の通路があります。 N 個の地点は 1 から N まで 1 つずつ番号が振られていて、 i 個目の通路は地点 v_{i} と地点 u_{i} を長さ w_{i} [m]で結んでいます。

埼大君は、そこである一風変わったスタンプラリーに参加しようとしています。
内容は、地点 a_{1} でスタートして最初にスタンプを押した後、地点 a_{2} から 地点 a_{K} まで、 K 個の地点を順番にめぐり、スタンプを押していくというものです。

このスタンプラリーには成績が付き、その成績は

• s_{i} :=地点a_{i} でスタンプを押してから地点a_{i+1} でスタンプを押すまでに移動した道のり[m]

と定義したときに、max({s_{i} | 1 ≤ i ≤ K-1})で表され、この値が小さいほど成績がよくなります。

地点同士は高々一本の通路で繋がっていて、通路同士は地点以外では交わりません。また、一方通行の通路はありません。すべての地点は、どの地点からでも徒歩で通路をたどれば必ずたどり着くことができます。

このスタンプラリーの変わった点は、参加者にはスタート時に Q 個の魔法の石が渡されることにあります。

この石にはそれぞれ相異なる数字 b_{1} ~ b_{Q} が書かれていて、この石を割ることで、その石が書かれている数字の地点までワープできます。
割った石は二度と使うことはできません。そして、ワープ中に移動した道のりは 0 メートルとして記録されます。
また、魔法の石はどの場所にいても使うことができます。したがって、対応する魔法の石があれば、ある地点からその次の地点に直接ワープすることもできます。
魔法の石は必ずしも使い切る必要はありません。

魔法の石を上手く活用することで、どこまで成績をよくできるか求めてください。

制約

• 2 \leq N \leq 300
• N-1 \leq M \leq N(N-1)/2
• 1 \leq v_i,u_i \leq N(1 \leq i \leq M)
• v_i \neq u_i(1\leq i \leq M)
• 1 \leq w_i \leq 10^9(1 \leq i \leq M)
• 2 \leq K \leq N
• 1 \leq a_i \leq N(1 \leq i \leq K)
• i \neq j なら a_i \neq a_j(1 \leq i,j \leq K)
• 0 \leq Q \leq N
• 1 \leq b_i \leq N(1 \leq i \leq Q)
• i \neq j なら b_i \neq b_j(1 \leq i,j \leq Q)

入力例 1

6 5
1 2 5
1 3 2
2 4 3
2 5 2
5 6 1
3
1 3 6
2
2 4

出力例 1

3

最初に地点1でスタートして、スタンプを押します。

その後、地点3まで徒歩で移動して、スタンプを押します。(s_1 = 2)

その後、2と書かれた魔法の石を割り、地点2までワープしたのち、地点6まで徒歩で移動してスタンプを押します。(s_2 = 3)

この行動がこのケースでは最適で、答えは3となります。