E. Just Tree Diameter
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes where the edges are weighted. The diameter of the tree is defined as the maximum weighted distance between any two nodes of the tree, where the weighted distance between two nodes is the sum of the edge weights on the simple path between them. You must write a program that finds the diameter of the given tree. Easy enough, right?

But wait, there's more! You will be given a set of updates to the tree. In a single update, you will add $$$x$$$ to the weights of all edges in the tree. Updates are persistent, meaning that once an update occurs, the next update will operate on the tree after all edge weights have been increased by $$$x$$$. After each update, you want to find the new diameter of the tree.

Input

The first line of input will consist of two integers $$$n$$$ ($$$2 \leq n \leq 10^5$$$) and $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — the number of nodes in the tree and the number of updates.

The following $$$n-1$$$ lines will consist of three integers $$$u$$$, $$$v$$$ ($$$1 \leq u, v \leq n$$$), and $$$w$$$ ($$$1 \leq w \leq 10^{12}$$$), denoting that there is an edge between node $$$u$$$ and node $$$v$$$ with initial weight $$$w$$$.

The following $$$m$$$ lines will consist of a single integer $$$x$$$ ($$$1 \leq x \leq 10^{12}$$$) denoting that $$$x$$$ gets added to every tree edge. It is guaranteed that the sum of $$$x$$$ across all updates will be at most $$$10^{12}$$$.

Output

Before the first update and after each update, output a line with a single integer corresponding to the current tree diameter.

Example
Input
7 2
3 7 5
1 3 3
3 4 1
1 6 7
1 5 2
5 2 4
1
2
Output
15
18
26