说明

扬非常热爱计算机科学，尤其是图论。因此，他每天在学校都会画一棵树，并且努力避免将笔从纸上抬起。

每天，他都会构思一棵包含 $N$ 个顶点的树，并从根节点开始绘制它。每条连接顶点 $a_i$ 和 $b_i$ 的边都有长度 $l_i$。他从根出发，沿着边移动，不抬笔，并希望至少经过每个顶点和每条边一次。由于独自画图对扬来说已经非常无聊，他决定邀请朋友帮忙。具体方式如下：当他在树上某个顶点完成绘制后，可以召唤一位朋友前来协助——该朋友必须从当前所在的顶点开始继续绘制，同样遵守“不抬笔”的限制。

扬最好的朋友阿蒂娜总是用敏锐的目光观察他的游戏。她根据公式 $L + k \times P$ 为每幅画打分，其中 $L$ 是扬和他的朋友们在纸上绘制的总路径长度（单位：厘米），$k$ 是扬召唤的朋友总数，而 $P$ 是“呼叫朋友”的费用——这个费用由扬在开始绘图前自行选定。请注意，如果某条边被多次遍历（即经过多次），其长度会在 $L$ 中被重复计算（见示例 1）。

为了让阿蒂娜尽可能高兴，扬希望选择一个价格 $P$，使得她的评分尽可能小。但由于作业繁重，他向你求助。对于每一天，他都设想了不同的“呼叫朋友”费用值 $P_i$，并想知道在最优绘图策略下，阿蒂娜可能给出的最小评分是多少。

输入格式

标准输入的第一行读入整数 $T$ —— 扬计划绘制的树的总数。随后依次给出每棵树的描述，以及你需要为扬解答的不同“呼叫朋友”费用值：

• 对于每棵树：第一行输入 $N$ —— 树中顶点的数量。
• 接下来 $N - 1$ 行，每行包含三个整数 $a_i, b_i, l_i$，分别表示连接两个顶点的一条边的端点及其长度。
• 然后输入一个整数 $Q$ —— 表示你需要处理的“呼叫朋友”费用的不同取值个数。
• 最后 $Q$ 行，每行一个整数 $P_i$，代表第 $i$ 种费用的具体数值。

输出格式

对于每一幅画（即每棵树），输出 $Q$ 个数字 —— 分别对应在“呼叫朋友”费用为 $P_i$ 时，扬通过最优绘图策略所能获得的、由阿蒂娜给出的最小评分。

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

90
100

提示

样例 1 解释

在样例测试中，扬只计划绘制一棵树。对于这棵树，存在两种可能的 $P$ 值。

示例 1： $P_1 = 10$

此时最优策略是召唤两位额外的朋友协助：

• 扬本人将沿路径 $1 - 2 - 4 - 2 - 5$ 行走；
• 随后他召唤“朋友 1”，从顶点 1 开始继续绘制；
• “朋友 1”将沿路径 $1 - 3 - 7$ 行走；
• 接着，“朋友 1”再召唤“朋友 2”，从顶点 3 开始继续绘制；
• “朋友 2”将沿路径 $3 - 6$ 行走。

最终评分为：
$L + k \times P = (30 + 30 + 10) + 2 \times 10 = 90$
（请注意：即使某条边已被画过，只要再次经过它，其长度仍会累加到最终结果中。）

示例 2： $P_2 = 100$

由于召唤朋友的代价过高，扬选择独自完成整棵树的绘制。可以证明，在这种情况下，他能达到的最小评分为 $100$。

限制条件

• $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$

所有测试数据中查询请求的总数不超过 $10^5$。

子任务

只有当成功通过某子任务所对应的所有测试点时，才能获得该子任务的分数。

翻译由 Qwen3.5-397B-A17B 完成