問題文
企鹅人厌倦了写题,所以他决定前往帕肯王国。
帕肯王国是 N 城市 1,\ 2,\ \ldots,\ N 和 N-1 由一条主干道组成。i 真正的道路是城市 u_i 和城市 v_i 双向绑扎,长度为 w_i 。您可以使用多条道路从任何城市前往任何城市。
企鹅人简介是一座城市 在 1 留在K 我试图通过重复“使用多条道路从当前城市移动到另一个城市”的动作来旅行。多次访问同一个城市是可以的,但由于企鹅人不喜欢步行,所以他们希望以最小化总步行距离的方式旅行。
顺便说一句,旅行时经常会发生意外。所以企鹅人 我决定提前回答以下关于i=1,\ 2,\ldots,\ Q 的问题。
- r_i 如果主干道无法通行,出行次数 定义 K 输出为 k_i 时,行驶总距离的最小值是多少?
制約
- 1\leq N,\ Q\leq10^5
- 1\leq u_i,\ v_i\leq N
- u_i≠v_i
- 1\leq w_i\leq 10^9
- 1\leq r_i\leq N-1
- 1\leq k_i\leq10^9
- 您可以使用多条道路从任何城市前往任何其他城市。
- 所有输入均为整数
小課題
- (200 点) N\leq2000,\ Q\leq2000
- (200 点) k_i 是常数 请输出超过
- (200 点) N\leq k_i
- (200 点) 没有其他限制。
入力
输入是按以下格式从标准输入给出的。
\(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 请输出问题的答案。
在每个问题中,企鹅人 如果您无法从 1 移动到任何其他城市。 如果可以移动 -1 ,请输出总移动距离的最小值。
入力例1
5 8 5 1 5 4 5 2 2 5 4 3 5 2 3 2 4 8 2 4 3 8 4 3 1 8 3 10 2 1
出力例1
7 19 11 19 9 -1 23 5
此示例是一个小作业。 满足 1,\ 4 约束。
作者: 企鹅人