Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Road Projects

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

Input

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.

Output

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.

Example

Input

7 2

1 2 18

2 3 22

3 4 24

4 7 24

2 6 4

3 5 12

1

100

Output

83

88

Note

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$$$.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 10:34:02 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|