AT_maximum_cup_2018_h Maxmin Tour

[problemUrl]: https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_h $ 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\

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ v_{1} $ $ u_{1} $ $ w_{1} $ $ : $ $ v_{M} $ $ u_{M} $ $ w_{M} $ $ K $ $ a_{1} $ $ ... $ $ a_{K} $ $ Q $ $ b_{1} $ $ ... $ $ b_{Q} $

最適な行動をした際の$ max({s_i\ |\ 1\

### 制約 - $ 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) $ ### Sample Explanation 1 最初に地点$ 1 $でスタートして、スタンプを押します。 その後、地点$ 3 $まで徒歩で移動して、スタンプを押します。$ (s_1\ =\ 2) $ その後、$ 2 $と書かれた魔法の石を割り、地点$ 2 $までワープしたのち、地点$ 6 $まで徒歩で移動してスタンプを押します。$ (s_2\ =\ 3) $ この行動がこのケースでは最適で、答えは$ 3 $となります。