Migrated from Lutece 1573 F0rest Park

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a park with $N$ spots, there are roads between some pairs of spots.

For each pair of spots, there is exactly one path between them, on which there are no spots passed more than once.

So it is obvious that there are $N - 1$ roads and $\frac{N(N - 1)}{2}$ paths.

The spots are labeled form $1$ to $N$, each road has a length and the length of a path is the sum of the length of the roads on it.

Let's sort all the paths by their lengths in the ascending order to form an ordered list, you need to answer $Q$ queries, each query asks the length of the $K_{th}$ path in these ordered list.

Input

The first line contains two integers $N$ and $Q$.

For the next $N - 1$ lines, each line contains three integers $u$, $v$, and $w$, denotes a road between the $u_{th}$ spot and the $v_{th}$ spot with the length $w$.

For the next $Q$ lines, each line contains an integer $K_i$, denotes a query.

$2 \leq N \leq 10^5$, $1 \leq Q \leq 10^5$, $1 \leq u, v \leq N$, $1 \leq K_i \leq \min\{\frac{N(N - 1)}{2}, 10^6\}$, $0 \leq w \leq 10^9$.

Output

For each query, print the corresponding answer in one line.

Samples

4 6
1 2 1
1 3 2
1 4 3
1
2
3
4
5
6

1
2
3
3
4
5

5 5
2 5 5
1 2 7
1 4 0
3 1 4
1
5
7
6
10

0
7
11
7
16

Resources

The 15th UESTC Programming Contest Final