Road Projects

## 题目描述 Berland 王国有 $n$ 座城市，有些城市间由双向道路连接，每条边不会出现超过一次。且每一条边都有它自己的长度。城市从 $1$ 到 $n$ 编号。 城市 $u$ 与 $v$ 间的旅行时间为 从 $u$ 到 $v$ 的最短路径上的边的边权之和。 在 Berland 王国的两座最重要的城市是 $1$ 与 $n$ 。 Berland 王国交通运输部决定修建一条新道路，来分担最重要的城市间的交通压力。然而，很多人已习惯了他们间的现在的旅行时间，因此新建的道路不应造成较大的影响。 新的道路应该建在 $u$ 与 $v$ 间，其中 $u≠v$ 且当前 $u$ 与 $v$ 间不存在道路。 他们提出了 $m$ 种可能的工程。每项工程都含有新建道路的长度 $x$ 。 Polycarp 在 Berland 王国交通运输部担任首席分析师，处理这 $m $ 项工程是他的工作。对于第 $i$ 项工程，他被要求选择城市 $u$ 和 $v$ 去建造这条道路使得 最重要的城市间 的旅行时间尽可能长。 不幸的是，Polycarp 不是程序员，世界上没有分析师能够仅使用笔和纸来处理所有项目。 因此，他要求你帮助他对于每个项目计算最重要的城市之间的最大可能的旅行时间。注意，对于不同的项目， $u$ 和 $v$ 的选择可以不同。 ## 输入格式 第一行包含两个整数 $n$ 和 $m$ ，( $ 3 \le n \le 3 \cdot 10^5 $ , $ 1 \le m \le 3 \cdot 10^5 $ )，——分别为城市的数量和工程的数目。 接下来 $ n - 1 $ 行每行包括三个整数 $ v_i $ , $ u_i $ and $ 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$ 个工程的两个最重要的城市间的最大的可能旅行时间。

There are $ n $ cities in the country of Berland. Some of them are connected by bidirectional roads in such a way that there exists exactly one path, which visits each road no more than once, between every pair of cities. Each road has its own length. Cities are numbered from $ 1 $ to $ n $ . The travelling time between some cities $ v $ and $ u $ is the total length of the roads on the shortest path from $ v $ to $ u $ . The two most important cities in Berland are cities $ 1 $ and $ n $ . The Berland Ministry of Transport decided to build a single new road to decrease the traffic between the most important cities. However, lots of people are used to the current travelling time between the most important cities, so the new road shouldn't change it too much. The new road can only be built between such cities $ v $ and $ u $ that $ v \neq u $ and $ v $ and $ u $ aren't already connected by some road. They came up with $ m $ possible projects. Each project is just the length $ x $ of the new road. Polycarp works as a head analyst at the Berland Ministry of Transport and it's his job to deal with all those $ m $ projects. For the $ i $ -th project he is required to choose some cities $ v $ and $ u $ to build the new road of length $ x_i $ between such that the travelling time between the most important cities is maximal possible. Unfortunately, Polycarp is not a programmer and no analyst in the world is capable to process all projects using only pen and paper. Thus, he asks you to help him to calculate the maximal possible travelling time between the most important cities for each project. Note that the choice of $ v $ and $ u $ can differ for different projects.

The first line contains two integers $ n $ and $ m $ ( $ 3 \le n \le 3 \cdot 10^5 $ , $ 1 \le m \le 3 \cdot 10^5 $ ) — the number of cities and the number of projects, respectively. Each of the next $ n - 1 $ lines contains three integers $ v_i $ , $ u_i $ and $ w_i $ ( $ 1 \le v_i, u_i \le n $ , $ 1 \le w_i \le 10^9 $ ) — the description of the $ i $ -th road. It is guaranteed that there exists exactly one path, which visits each road no more than once, between every pair of cities. Each of the next $ m $ lines contains a single integer $ x_j $ ( $ 1 \le x_j \le 10^9 $ ) — the length of the road for the $ j $ -th project.

Print $ m $ lines, the $ j $ -th line should contain a single integer — the maximal possible travelling time between the most important cities for the $ j $ -th project.

7 2
1 2 18
2 3 22
3 4 24
4 7 24
2 6 4
3 5 12
1
100

83
88

The road network from the first example:  You can build the road with length $ 1 $ between cities $ 5 $ and $ 6 $ to get $ 83 $ as the travelling time between $ 1 $ and $ 7 $ ( $ 1 \rightarrow 2 \rightarrow 6 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 7 $ $ = $ $ 18 + 4 + 1 + 12 + 24 + 24 = 83 $ ). Other possible pairs of cities will give answers less or equal to $ 83 $ .