AT_pakencamp_2020_day2_g 旅人計画問題

[problemUrl]: https://atcoder.jp/contests/pakencamp-2020-day2/tasks/pakencamp_2020_day2_g 配点 : $ 800 $ 点 penguinman は作問作業に疲れたため、パ研王国を旅することにしました。 パ研王国は $ N $ 個の都市 $ 1,\ 2,\ \ldots,\ N $ と $ N-1 $ 本の道路からなります。$ i $ 本目の道路は都市 $ u_i $ と都市 $ v_i $ を双方向に結んでいて、長さは $ w_i $ です。任意の都市から任意の都市まで、いくつかの道路を用いることで移動することができます。 はじめ penguinman は都市 $ 1 $ にいて、$ K $ 回に渡って「今いる都市からいくつかの道路を使って他の都市へ移動する」という行動を繰り返すことで旅をしようとしています。同じ都市を複数回訪れても構いませんが、penguinman は歩くのが嫌いなため、歩く距離の合計が最小になるように旅をしたいです。 ところで、旅にはアクシデントがつきものです。そこで penguinman は、$ i=1,\ 2,\ldots,\ Q $ について以下の質問に事前に答えておくことにしました。 - $ r_i $ 本目の道路が通れなくなったとして、移動回数 $ K $ を $ k_i $ と定めた時の移動距離の合計の最小値はいくつか。 これらの質問全てに答え切ることは、penguinman には難しすぎました。彼の代わりにこれらの質問全てに答えてあげてください。

入力は以下の形式で標準入力から与えられます。 ``` \(N\) \(Q\) \(u_1\) \(v_1\) \(w_1\) \(u_2\) \(v_2\) \(w_2\) \(︙\) \(u_{N-1}\) \(v_{N-1}\) \(w_{N-1}\) \(r_1\) \(k_1\) \(r_2\) \(k_2\) \(︙\) \(r_Q\) \(k_Q\) ```

$ i $ 行に渡って出力してください。$ i $ 行目には $ i $ 個目の質問への答えを出力してください。 それぞれの質問において、penguinman が都市 $ 1 $ から任意の他の都市へ移動できない場合は $ -1 $ を、移動出来る場合は移動距離の合計の最小値を出力してください。

### 小課題 1. $ (200 $ 点$ ) $ $ N\leq2000,\ Q\leq2000 $ 2. $ (200 $ 点$ ) $ $ k_i $ は一定 3. $ (200 $ 点$ ) $ $ N\leq\ k_i $ 4. $ (200 $ 点$ ) $ 追加の制約はない。