Problem AB6. Tree

Yan loves computer science, and graph theory in particular. Therefore, every day at school, he draws a tree, trying not to lift his pen from the paper.

Every day, he invents a tree with $N$ vertices and starts drawing it from the root. Each edge connecting vertices $a_i$ and $b_i$ has a length $l_i$. Starting from the root, he moves along the edges without lifting his pen, wanting to visit every vertex and edge at least once.

Since Yan is getting bored of drawing by himself, he decides to involve his friends in the drawing process. This happens as follows: after some vertex of the tree has been drawn, Yan can call a friend for help, who will start drawing from that vertex, while still following the constraint of not lifting the pen from the paper.

Yan's best friend, Athena, always watches Yan's game with a keen eye. She evaluates each drawing with a score calculated by the formula $L + k * P$, where $L$ is the total length in centimeters that the pens of Yan and his friends have drawn on the paper, $k$ is the total number of friends Yan has called, and $P$ is the "call a friend" fee that Yan chooses before he starts drawing. Note that in $L$, the length of an edge can be counted multiple times if it is traversed multiple times (see Example 1).

Since Yan wants to please Athena as much as possible, he wants to choose a price $P$ such that Athena's score is as small as possible. Because Yan has a lot of homework, he asks you for help. For each day, he has in mind different values $P_i$ for the "call a friend" fee, and for each of them, he wonders what the minimum score is that Athena can give him with an optimal drawing.

Input

The first line of standard input contains $T$ – the number of tree drawings Yan wants to make. The descriptions of the trees and the different values of the fee for which you need to find the answer follow: The first line contains $N$ – the number of vertices in the tree. The next $N - 1$ lines each contain $a_i, b_i$ and $l_i$ – the two endpoints and the length of each edge. The next line contains $Q$ – the number of different values for the "call a friend" fee for which you need to solve the problem. The next $Q$ lines each contain one number – $P_i$, the value of this fee.

Output

For each drawing, you must output $Q$ numbers – the minimum score Yan can get for each drawing if calling a friend costs $P_i$.

Constraints

$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$ The sum of the number of queries across all test cases is $\le 10^5$.

Subtasks

Points for a given subtask are awarded only if all test cases provided for it are passed successfully.

Examples

Input 1

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

Output 1

90
100

Note 1

In the example test, there is only 1 tree that Yan wants to draw. For this tree, there are 2 possible values for $P$.

Example 1: $P_1 = 10$ Here, the optimal solution consists of calling two additional friends: Yan will traverse the path: $1 - 2 - 4 - 2 - 5$, after which he will call Friend 1 for help, who will start at vertex 1. Friend 1 will traverse the path $1 - 3 - 7$, after which they will call Friend 2 for help, who will start at vertex 3. Friend 2 will traverse the path $3 - 6$. Thus, the final score is $L + k * P = (30 + 30 + 10) + 2 * 10 = 90$ (note that even if an edge has already been drawn, its length is added to the final result when it is traversed again).

Example 2: $P_2 = 100$ Here, due to the very high cost of calling a friend, Yan will draw the entire tree by himself. Thus, it can be proven that the minimum score he can achieve is 100.