AT_abc369_e [ABC369E] Sightseeing Tour

[problemUrl]: https://atcoder.jp/contests/abc369/tasks/abc369_e $ N $ 個の島と、$ 2 $ つの島の間を双方向に結ぶ $ M $ 本の橋があり、 それぞれ島 $ 1 $, 島 $ 2 $, $ \ldots $, 島 $ N $ および 橋 $ 1 $, 橋 $ 2 $, $ \ldots $, 橋 $ M $ と番号づけられています。 橋 $ i $ は島 $ U_i $ と島 $ V_i $ を相互に結んでおり、どちらの方向に移動するにも $ T_i $ だけ時間がかかります。 ここで、橋の両端が同一の島であるような橋は存在しませんが、ある $ 2 $ つの島の間が $ 2 $ 本以上の橋で直接繋がれている可能性はあります。 また、どの $ 2 $ つの島の間もいくつかの橋をわたって移動することができます。 $ Q $ 個の問題が与えられるので、各問題に対する答えを求めてください。$ i $ 番目の問題は次のようなものです。 > 相異なる $ K_i $ 本の橋、橋 $ B_{i,1} $, 橋 $ B_{i,2} $, $ \ldots $, 橋 $ B_{i,K_i} $ が与えられます。 > これらの橋をすべて $ 1 $ 回以上わたり、島 $ 1 $ から島 $ N $ まで移動するために必要な時間の最小値を求めてください。 > ただし、島 $ 1 $ から島 $ N $ までの移動において、橋をわたって島の間を移動するのにかかる時間以外は無視できるものとします。 > また、与えられた橋はどの順で、またどの向きにわたってもかまいません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ U_1 $ $ V_1 $ $ T_1 $ $ U_2 $ $ V_2 $ $ T_2 $ $ \vdots $ $ U_M $ $ V_M $ $ T_M $ $ Q $ $ K_1 $ $ B_{1,1} $ $ B_{1,2} $ $ \cdots $ $ B_{1,{K_1}} $ $ K_2 $ $ B_{2,1} $ $ B_{2,2} $ $ \cdots $ $ B_{2,{K_2}} $ $ \vdots $ $ K_Q $ $ B_{Q,1} $ $ B_{Q,2} $ $ \cdots $ $ B_{Q,{K_Q}} $

$ Q $ 行出力せよ。$ i $ 行目（$ 1\leq\ i\leq\ Q $）には $ i $ 番目の問題に対する答えを整数で出力せよ。

### 制約 - $ 2\leq\ N\ \leq\ 400 $ - $ N-1\leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\leq\ U_i\