题目描述

给定一棵树，求所有经过点数大于等于二的无向路径中长度第 $k$ 小的。多组询问。

输入格式

第一行两个整数 $n,q$，分别为点数和询问数。

接下来 $n-1$ 行，每行三个整数 $x,y,z$，表示 $x$ 到 $y$ 的边长度为 $z$。

接下来 $q$ 行，每行一个整数 $k$。保证存在至少 $k$ 条路径。

输出格式

$q$ 行，每行一个整数，为答案。

样例

输入

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

输出

3
3
4
6
7
7

说明

本题捆绑测试，时间限制 $3$ 秒。

对于 $100\%$ 的数据，$1\le n\le 5\times 10^4$，$1\le q\le 2\times 10^5$，$1\le x,y\le n$，$1\le \sum z\le 2\times 10^5$。详细数据范围如下。

Subtask 1（10 pts）：$n,q\le 200$。

Subtask 2（10 pts）：$n,q\le 10^3$。

Subtask 3（10 pts）：$n\le 10^3$。

Subtask 4（10 pts）：$q\le 10$。

Subtask 5（60 pts）：没有任何附加限制。