小Z的树迁移
题号：NC281601
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小Z生活在树上，这一天他计划将他的住所向下迁移。
现在给出一颗有 n 个结点且以 1 结点为根的树，树上的每一条边都有一个权值。有 q 个询问，每一次询问给出两个数 u 和 d，其中 u 表示小Z目前居住的结点，d 表示小Z计划向下移动的次数。小Z希望向下移动的路径上的边的权值和最大，请你输出能得到的最大权值。如果没有合法路径，输出 -1。

输入描述:

第一行包含一个整数 n(1 \leqq n \leqq 10^5)，表示树的结点数。

接下来的 n-1 行，每行包含三个整数 a, b, w(1 \leqq a, b \leqq n; 1 \leqq w \leqq 10^9)，表示结点 a 和结点 b 之间有一条权值为 w 的边 。

接下来一行输入一个整数 q(1 \leqq q \leqq 10^5)，表示询问次数。

接下来的 q 行，每行包含两个整数 u, d(1 \leqq u \leqq n; 1\leqq d \leqq n)，表示小Z目前居住的结点和计划向下移动的次数。

输出描述:

对于每一个询问，输出小Z能够得到的最大权值和。如果没有合法路径，输出 -1。
示例1

输入

复制 
5
1 2 3
1 3 5
2 4 2
2 5 1
3
1 2
2 1
3 2

输出

复制 
5
2
-1

说明

第一个查询中，从结点 1 向下移动 2 次，路径为 1 \to 2 \to 4，权值和为 3 + 2 = 5。
第二个查询中，从结点 2 向下移动 1 次，路径为 2 \to 4，权值和为 2。
第三个查询中，从结点 3 向下移动 2 次没有合法路径，输出 -1。