Longest Chain in a Dynamic Weighted Tree

You are given a rooted tree with N nodes (numbered from 0 to N-1) and each edge has a weight. Node 0 is the root.

For a node u, define its value f(u) as the length of the longest chain passing through node u in the subtree rooted at u. In other words, if we define for each node u a value \[ best(u)=\max_{v\in child(u)}\{w(u,v)+best(v)\}\] (with the convention that when u has no child, best(u)=0), then \[ f(u)=\max\Bigl( best(u), \max_{\substack{v, w \in child(u)\\v\neq w}} \{ (w(u,v)+best(v)) + (w(u,w)+best(w)) \} \Bigr). \] Note that the chain considered for f(u) must pass through u and can extend in at most two different directions from u.

There are Q operations. In each operation, you will add a positive value to the weight of one edge. You are required to output the value of \[ S=\left(\sum_{i=1}^{N-1} f(i)\right)\bmod (10^9+7) \] before any operations and after each operation.

Note: In each update, the edge to update is given by two endpoints. Since the tree is rooted at 0, the parent is the one with smaller depth.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers N and Q representing the number of nodes and the number of operations.
2. Then follow N-1 lines, each containing three integers u, v, and w. This indicates an edge connecting nodes u and v with weight w. It is guaranteed that the tree is rooted at node 0; that is, in each edge, the node with the smaller depth is considered the parent.
3. Then follow Q lines, each containing three integers u, v, and d. This means that you add the value d (a positive integer) to the weight of the edge connecting nodes u and v (you should determine which endpoint is the parent based on the tree structure).

outputFormat

Output Q+1 lines. The first line should contain the initial value of \( S \) (i.e. before any operations). Then, after each operation, output a line containing the updated value of \( S \) modulo \(10^9+7\).

sample

3 1
0 1 1
0 2 2
0 1 3

0
0