这是该问题的简单版本。两个版本之间的区别在于，在此版本中，$q \le 10$。只有当你解决了该问题的所有版本时，才能进行 Hack。

给你一棵含有 $n$ 个节点的树，节点编号为 $1$ 到 $n$。每条边都被分配了一个正整数边权 $w_1, w_2, \dots, w_{n-1}$。

一个胜利染色是指将每个节点染成红、黄两色之一，且必须有至少一个节点被染成红色（对应 T1 战队的标志）。

假设每个节点都被分配了一个非负整数点权 $x_1, x_2, \dots, x_n$。一个胜利染色的代价定义为所有红色节点的点权之和，加上连接不同颜色（红色和黄色）节点的边权之和。我们定义 $f([x_1, x_2, \dots, x_n])$ 为所有胜利染色中可能达到的最小代价。

Gumayusi 考虑了在给定序列 $x_1, x_2, \dots, x_n$ 的情况下计算 $f([x_1, x_2, \dots, x_n])$ 的问题。然而，这个问题对他来说太简单了，于是他设计了一个变种：给定一个整数 $l$，寻找一个非负整数点权序列 $[x_1, x_2, \dots, x_n]$，使得 $f([x_1, x_2, \dots, x_n]) \ge l$，且总和 $\sum_{i=1}^n x_i$ 最小。

Gumayusi 很满意，但存在一个严重的问题——这个问题没有任何询问，而询问是任何一个好题必不可少的组成部分。因此，他为这个问题添加了询问。对于作为询问给出的每个 $l$，你必须求出对应的最小可能点权和。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 250\,000$）—— 节点的数量。

接下来的 $n - 1$ 行，每行包含三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$，$u_i \ne v_i$）—— 表示一条连接节点 $u_i$ 和 $v_i$ 且边权为 $w_i$ 的边。

保证这些边构成一棵树。

下一行包含一个整数 $q$（$1 \le q \le 10$）—— 询问的数量。

接下来的 $q$ 行，每行包含一个整数 $l_i$（$1 \le l_i \le 10^9$）—— 第 $i$ 个询问的参数。

保证所有测试用例中 $n$ 的总和不超过 $250\,000$。

注意，对 $q$ 的总和没有显式的上限。

输出格式

对于每个询问，输出一行表示答案。

样例

输入样例 1

2
5
3 5 10
2 3 4
3 1 10
3 4 2
5
28
32
11
17
23
2
1 2 3
1
1

输出样例 1

88
108
21
42
66
1

说明

以下列表显示了第一个测试用例中每个询问的一种可能的最佳点权分配：

• $[18, 24, 2, 26, 18]$
• $[22, 28, 6, 30, 22]$
• $[4, 7, 0, 9, 1]$
• $[7, 13, 0, 15, 7]$
• $[13, 19, 0, 21, 13]$