Mining Gold!

Gold Bar Lot. Photo by Pixabay

It has been a long, tiring week of tests at UCLA. Your
friend wants to cheer you up, so he invites you over to his
dorm to play a new game he recently purchased: *Mining Gold!*

In the game, you are the owner of a goldmine. Your
underground tunnel network can be represented as a rooted tree
with $n$ different
checkpoints, with the tree rooted at checkpoint $1$. Each tunnel connects exactly two
checkpoints, and has a *transportation
value*, which is the amount of gold that can be gained by
travelling through that tunnel between the checkpoints. It
turns out, some tunnels are very poorly built so every time you
travel through that tunnel you need to use some gold to hire a
guide! Thus, some edges may have a negative *transportation value*.

Your friend is curious about the gold transportation within
the goldmine and asks you to answer $q$ queries, where each query gives a
single integer $x$
$(1 \leq x \leq n)$. For
each integer $x$, your
friend asks you, "If you travel along some simple path while
staying in the subtree of $x$, what’s the smallest amount of
gold you can possibly gain?" In other words, you want to find
the minimum sum of *transportation values*
of all the tunnels traveled through if you start at checkpoint
$x$ and travel to some
checkpoint in its subtree without visiting any checkpoint twice
and without ever leaving the subtree of $x$.

The first line of input gives $n$ and $q$ $(1 \leq n, q \leq 2 \cdot 10^5)$, the number of checkpoints and queries, respectively.

The next $n - 1$ lines will give three integers per line in the form $a$ $b$ $c$, denoting an edge between checkpoints $a$ and $b$ $(1 \leq a, b \leq n, a \neq b)$ with transportation value $c$ $(-10^9 \leq c \leq 10^9)$.

The next $q$ lines will give a single integer $x$, the checkpoint in which to process the current query.

Output $q$ lines, where the $i^{th}$ line will contain the answer to the $i^{th}$ query.

Sample Input 1 | Sample Output 1 |
---|---|

4 4 1 2 -1 2 3 2 2 4 3 4 2 3 1 |
0 2 0 -1 |

Sample Input 2 | Sample Output 2 |
---|---|

1 2 1 1 |
0 0 |

Sample Input 3 | Sample Output 3 |
---|---|

5 5 1 2 1 2 3 -2 3 4 3 4 5 -4 1 2 3 4 5 |
-2 -3 -1 -4 0 |