Dynamic Tree Diameter

You are given a tree with n nodes and weighted edges. The tree is modified online: there are q queries, and each query updates the weight of one edge in the tree. After each update, you are required to compute the sum of the weights on the diameter of the tree. Here, the diameter is defined as the longest path between any two nodes in the tree. In this problem, all formulas are written in LaTeX. For example, the number of nodes is denoted by $n$, and the update is given as: update the weight of the $i$-th edge to $w_{new}$.

Note: This problem must be solved online.

inputFormat

The first line contains two integers $n$ and $q$, representing the number of nodes and the number of queries, respectively. The next $n-1$ lines each contain three integers $u$, $v$, and $w$, representing an edge between nodes $u$ and $v$ with weight $w$. Then, $q$ lines follow, each containing two integers $id$ and $w_{new}$, which means that the weight of the $id$-th edge (the edges are numbered from $1$ to $n-1$ in the input order) is updated to $w_{new}$.

outputFormat

For each query, output one integer on a separate line: the sum of the weights along the diameter (i.e. the longest path) of the current tree after the update.

sample

4 3
1 2 3
2 3 4
2 4 5
2 6
3 2
1 1

11
9
8