贝尔兰 的国家有 $$$n$$$ 城市。其中一些是通过双向道路连接的,每对城市之间都存在一条路径,该路径访问每条道路不超过一次。每条路都有自己的长度。城市编号从 $$$1$$$ 到 $$$n$$$。
部分城市$$$v$$$和$$$u$$$之间的行驶时间是从$$$v$$$到$$$u$$$的最短路径上的道路总长度。
伯兰最重要的两个城市是城市 $$$1$$$ 和 $$$n$$$。
贝尔兰交通部决定修建一条新道路,以减少最重要城市之间的交通流量。然而,很多人已经习惯了目前在最重要城市之间的出行时间,因此新道路应该不会改变太多。
新道路只能在 $$$v$$$ 和 $$$u$$$ 之间修建,且 $$$v \neq u$$$ 和 $$$v$$$ 和 $$$u$$$ 尚未通过某些道路连接。
他们提出了 $$$m$$$ 可能的项目。每个项目只是新道路的长度$$$x$$$。
Polycarp 是 Berland 交通部的首席分析师,他的工作就是处理所有这些 $$$m$$$ 项目。对于第 $$$i$$$ 个项目,他需要选择一些城市 $$$v$$$ 和 $$$u$$$ 来修建长度为 $$$x_i$$$ 的新道路,以使最重要城市之间的旅行时间尽可能长。
不幸的是,Polycarp 不是程序员,世界上没有分析师能够仅使用笔和纸处理所有项目。
因此,他要求您帮助他计算每个项目在最重要城市之间的最大可能旅行时间。请注意,对于不同的项目,$$$v$$$ 和 $$$u$$$ 的选择可能有所不同。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$) — 分别是城市数量和项目数量。
接下来的 $$$n - 1$$$ 行包含三个整数 $$$v_i$$$、$$$u_i$$$ 和 $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$1 \le w_i \le 10^9$$$) — 第 $$$i$$$ 路的描述。保证每对城市之间恰好存在一条路径,且该路径访问每条道路不超过一次。
接下来的 $$$m$$$ 行都包含一个整数 $$$x_j$$$ ($$$1 \le x_j \le 10^9$$$) — 第 $$$j$$$ 个项目的道路长度。
输出
打印 $$$m$$$ 行,第 $$$j$$$ 行应包含一个整数 - 第 $$$j$$$ 项目的最重要城市之间的最大可能旅行时间。
示例
输入 #1
7 2 1 2 18 2 3 22 3 4 24 4 7 24 2 6 4 3 5 12 1 100
输出 #1
83 88
注意
第一个示例中的道路网络:
您可以在城市 $$$5$$$ 和 $$$6$$$ 之间修建长度为 $$$1$$$ 的道路,得到 $$$83$$$ 作为 $$$1$$$ 和 $$$7$$$ 之间的行驶时间 ($$$1 \rightarrow 2 \rightarrow 6 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 7$$$ $$$=$$$ $$$18 + 4 + 1 + 12 + 24 + 24 = 83$$$)。其他可能的城市对将给出小于或等于 $$$83$$$ 的答案。