AT_maximum_cup_2018_h Maxmin Tour

有一个图，图中包含 $N$ 个地点和 $M$ 条无向通路。这些地点编号从 1 到 $N$。第 $i$ 条通路把地点 $v_i$ 和地点 $u_i$ 连接起来，通路长度为 $w_i$ 米。 有一位名叫埼大君的选手，准备参加一场特别的盖章比赛。比赛要求他从地点 $a_1$ 开始，依次访问 $K$ 个指定地点 $a_2$ 至 $a_K$，在每个地点盖上邮戳。要取得好成绩，需在任何连续两个地点 $a_i$ 和 $a_{i+1}$ 之间旅行的最远距离 $s_i$ 最小。成绩用 $\max(s_i \mid 1 \le i \le K-1)$ 表示，数值越小越好。 在此图中，任何两个地点之间最多只有一条通路连接，通路除了在交点外不会交汇。此外，没有单向通路，任意两点之间均可步行到达。 比赛的特殊之处在于选手开始时获赠 $Q$ 块魔法石。每块石头上标有一个不同的地点数字 $b_1$ 到 $b_Q$，使用一块魔法石即可瞬间传送到相应的地点。传送过程中的距离视为 0 米，这些石头可以在任何位置使用。即使有魔法石，也不需全部用完。 你需要确定，怎么利用魔法石能使成绩最好。

输入通过标准输入给出，格式如下： > $N$ $M$，然后是 $M$ 个三元组 $(v_i, u_i, w_i)$，接着 $K$ 个数 $a_1, a_2, \ldots, a_K$，再接着是 $Q$ 个数 $b_1, b_2, \ldots, b_Q$。

输出一行，用来表示在最优选择下的最大移动距离 $\max(s_i \mid 1 \le i \le K-1)$。

- $2 \le N \le 300$ - $N-1 \le M \le N(N-1)/2$ - $1 \le v_i, u_i \le N, \, v_i \neq u_i$ - $1 \le w_i \le 10^9$ - $2 \le K \le N$ - $1 \le a_i \le N, \, a_i$ 互不相同 - $0 \le Q \le N$ - $1 \le b_i \le N, \, b_i$ 互不相同 ### 示例解释 首先在地点 1 盖上邮戳，然后走到地点 3 再盖上邮戳。此时 $s_1 = 2$。接着使用写有 2 的魔法石传送到地点 2，然后从 2 走到 6 并盖上邮戳。此时 $s_2 = 3$。这是这个情况下的最优方案，所以答案是 3。 **本翻译由 AI 自动生成**