Jan 非常热爱计算机科学，尤其是图论。因此，他每天在学校都会画一棵树，并尽量不让笔离开纸面。

每天他都会构思一棵有 $N$ 个顶点的树，并从根节点开始绘制。每条连接顶点 $a_i$ 和 $b_i$ 的边都有长度 $l_i$。从根节点开始，他沿着边移动，不抬起笔，并希望至少经过所有的顶点和边一次。

由于 Jan 独自画树感到非常无聊，他决定邀请朋友们参与绘制。具体方式如下：在绘制完树上的某个顶点后，Jan 可以叫一位朋友来帮忙，这位朋友从该顶点开始继续绘制，同样必须遵守不抬起笔的限制。

Jan 最好的朋友 Athena 总是用敏锐的目光观察 Jan 的游戏。她根据公式 $L + k * P$ 对每幅画进行评分，其中 $L$ 是 Jan 和他的朋友们在纸上绘制的总长度（以厘米为单位），$k$ 是 Jan 邀请的朋友总数，$P$ 是 Jan 在开始绘制前选择的“呼叫朋友”费用。请注意，在 $L$ 中，如果某条边被多次经过，则该边的长度会被计算多次（参见样例 1）。

由于 Jan 想尽可能让 Athena 高兴，他希望选择一个费用 $P$，使得 Athena 给出的评分尽可能小。由于 Jan 有很多家庭作业，他向你寻求帮助。对于每一天，他都有不同的“呼叫朋友”费用 $P_i$ 的预想值，他想知道对于每一个 $P_i$，在最优绘制方案下，Athena 可能给出的最小评分是多少。

输入格式

标准输入的第一行包含 $T$ —— Jan 想要绘制的树的数量。接下来是树的描述以及需要求解的费用值：第一行输入 $N$ —— 树中的顶点数。接下来的 $N-1$ 行，每行包含 $a_i, b_i$ 和 $l_i$ —— 每条边的两个端点和长度。接下来是一个数字 $Q$ —— 需要求解的“呼叫朋友”费用的不同值数量。接下来的 $Q$ 行，每行包含一个数字 $P_i$ —— 该费用的值。

输出格式

对于每棵树，输出 $Q$ 个数字 —— 如果呼叫朋友的费用为 $P_i$，Jan 在每棵树上能获得的最小评分。

数据范围

$1 \le T \le 5$ $1 \le N \le 10^5$ $1 \le Q \le 10^5$ $1 \le l_i \le 10^9$ $1 \le P_i \le 10^9$ 所有测试中查询总数 $\le 10^5$

子任务

样例

输入 1

1
7
1 2 10
1 3 10
2 4 5
2 5 10
3 6 10
3 7 20
2
10
100

输出 1

90
100

说明 1

在示例测试中，只有 1 棵 Jan 想要绘制的树。对于这棵树，有 2 个可能的 $P$ 值。

示例 1：$P_1 = 10$ 这里最优解包括呼叫两名额外的朋友： Jan 将走过路径：$1 - 2 - 4 - 2 - 5$，之后他呼叫朋友 1 从顶点 1 开始帮忙。 朋友 1 将走过路径 $1 - 3 - 7$，之后呼叫朋友 2 从顶点 3 开始帮忙。 朋友 2 将走过路径 $3 - 6$。 因此最终评分为 $L + k * P = (30 + 30 + 10) + 2 * 10 = 90$（注意，即使某条边已经被绘制过，当再次经过它时，其长度仍会加到最终结果中）。

示例 2：$P_2 = 100$ 这里由于呼叫朋友的费用太高，Jan 将独自绘制整棵树。可以证明，他能达到的最小评分为 100。