AT_pakencamp_2020_day2_g 旅人計画問題

有一张由 $n$ 个点（编号 $1$ 到 $n$）和 $n-1$ 条边（编号 $1$ 到 $n-1$）构成的无向图。第 $i$ 条边连接点 $u_i$ 和 $v_i$，边权为 $w_i$。 有一枚棋子现在正放在图中的点 $1$ 处。去掉第 $r$ 条边。重复执行 $k$ 次“从当前点使用一条边向其他点移动”，前提是使得所使用的边的边权和最小。同一个点可以重复访问。请求出这个值。 输入含有多组询问。

第一行输入点数 $n$ 和询问次数 $q$。 第二行到第 $n$ 行，每行输入一条边的信息 $u_i,v_i,w_i$。 从第 $n+1$ 行起的 $q$ 行，每行输入两个数 $r,k$，表示删去的边的编号及移动次数。

输出 $q$ 行。若棋子可以移动，输出移动距离的最小值；否则输出 $-1$。 ### 数据规模与约定 - $1 \le n,q \le 10^5$； - $1 \le u_i,v_i \le n$，$u_i \neq v_i$，$1 \le w_i \le 10^9$； - $1 \le r \le n-1$，$1 \le k \le 10^9$； - 保证图联通。 - 输入数据均为整数。

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