{"raw_statement":[{"iden":"statement","content":"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$.\n\nThe travelling time between some cities $v$ and $u$ is the total length of the roads on the shortest path from $v$ to $u$.\n\nThe two most important cities in Berland are cities $1$ and $n$.\n\nThe 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.\n\nThe 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.\n\nThey came up with $m$ possible projects. Each project is just the length $x$ of the new road.\n\nPolycarp 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**.\n\nUnfortunately, Polycarp is not a programmer and no analyst in the world is capable to process all projects using only pen and paper.\n\nThus, 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."},{"iden":"input","content":"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.\n\nEach 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.\n\nEach 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."},{"iden":"output","content":"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."},{"iden":"example","content":"Input\n\n7 2\n1 2 18\n2 3 22\n3 4 24\n4 7 24\n2 6 4\n3 5 12\n1\n100\n\nOutput\n\n83\n88"},{"iden":"note","content":"The road network from the first example:\n\n![image](https://espresso.codeforces.com/112687c8a4cdc67ef1497a582b6ceef40762e46f.png)\n\nYou 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$."}],"translated_statement":[{"iden":"statement","content":"在伯兰国中有 $n$ 座城市。其中一些城市通过双向道路相连，使得任意两座城市之间恰好存在一条路径，该路径每条道路至多经过一次。每条道路都有其自身的长度。城市编号从 $1$ 到 $n$。\n\n城市 $v$ 和 $u$ 之间的旅行时间是 $v$ 到 $u$ 的最短路径上所有道路长度的总和。\n\n伯兰国最重要的两座城市是城市 $1$ 和城市 $n$。\n\n伯兰交通部决定修建一条新道路，以减少这两座最重要城市之间的交通压力。然而，许多人已经习惯了当前这两座城市之间的旅行时间，因此新道路不应使该时间改变太多。\n\n新道路只能在满足 $v \\ne u$ 且 $v$ 和 $u$ 之间尚未有道路直接连接的两座城市之间修建。\n\n他们提出了 $m$ 个可能的项目。每个项目仅指定新道路的长度 $x$。\n\n波利卡尔普是伯兰交通部的首席分析师，他的职责是处理所有这些 $m$ 个项目。对于第 $i$ 个项目，他需要选择两座城市 $v$ 和 $u$，修建一条长度为 $x_i$ 的新道路，使得最重要城市之间的旅行时间达到**最大可能值**。\n\n不幸的是，波利卡尔普不是程序员，世界上没有任何分析师能仅凭纸笔处理所有项目。\n\n因此，他请求你帮助他计算每个项目中，最重要城市之间可能达到的最大旅行时间。注意，不同项目中选择的 $v$ 和 $u$ 可以不同。\n\n第一行包含两个整数 $n$ 和 $m$（$3 \\le n \\le 3 \\cdot 10^5$，$1 \\le m \\le 3 \\cdot 10^5$）——分别表示城市数量和项目数量。\n\n接下来的 $n - 1$ 行，每行包含三个整数 $v_i$、$u_i$ 和 $w_i$（$1 \\le v_i, u_i \\le n$，$1 \\le w_i \\le 10^9$）——表示第 $i$ 条道路的描述。保证任意两座城市之间恰好存在一条路径，该路径每条道路至多经过一次。\n\n接下来的 $m$ 行，每行包含一个整数 $x_j$（$1 \\le x_j \\le 10^9$）——表示第 $j$ 个项目中新道路的长度。\n\n请输出 $m$ 行，第 $j$ 行应包含一个整数——表示第 $j$ 个项目中，最重要城市之间可能达到的最大旅行时间。\n\n第一个示例的道路网络：\n\n\n\n你可以修建一条长度为 $1$ 的道路连接城市 $5$ 和 $6$，使得城市 $1$ 和 $7$ 之间的旅行时间为 $83$（路径 $1 \\to 2 \\to 6 \\to 5 \\to 3 \\to 4 \\to 7$ 的长度为 $18 + 4 + 1 + 12 + 24 + 24 = 83$）。其他可能的城市对给出的答案均小于或等于 $83$。"},{"iden":"input","content":"第一行包含两个整数 $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$ 个项目中新道路的长度。"},{"iden":"output","content":"请输出 $m$ 行，第 $j$ 行应包含一个整数——表示第 $j$ 个项目中，最重要城市之间可能达到的最大旅行时间。"},{"iden":"note","content":"第一个示例的道路网络：你可以修建一条长度为 $1$ 的道路连接城市 $5$ 和 $6$，使得城市 $1$ 和 $7$ 之间的旅行时间为 $83$（路径 $1 \\to 2 \\to 6 \\to 5 \\to 3 \\to 4 \\to 7$ 的长度为 $18 + 4 + 1 + 12 + 24 + 24 = 83$）。其他可能的城市对给出的答案均小于或等于 $83$。"}],"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}