Youxiang is playing a very interesting strategy game. The map of this game is not actually very large, and Youxiang can still manage it. However, for some reason, the game developers are making the maps larger and larger, to the point where Youxiang can no longer see the whole map at a glance, let alone fight others.

Before the battle, Youxiang has a very basic problem to solve.

The entire map is a tree structure with $n$ nodes, and these nodes are connected by $n-1$ edges, such that there is a unique path between any two nodes. In the game, Youxiang can add or remove some troops at any node. Youxiang can also place a supply station at any node.

If a supply station is placed at node $u$, and there are $d_v$ troops at node $v$, then Youxiang must pay $d_v \cdot \text{dist}(u, v)$ in currency to supply these troops. Therefore, if Youxiang needs to supply all troops, the total cost Youxiang has to pay is $\sum_{v=1}^n d_v \cdot \text{dist}(u, v)$. Here, $\text{dist}(u, v)$ represents the distance between node $u$ and node $v$ on the tree (the weight of the unique path).

Because of the game's rules, Youxiang can choose one node to be the supply station. During the game, Youxiang may create some troops at certain nodes or reduce the number of troops at certain nodes. After such operations, for economic reasons, Youxiang often moves her supply station to save some money. But because the map of this game is too large, Youxiang cannot easily make the optimal arrangement. Can you help her?

You can assume that there are no troops at any node initially.

Input

The first line contains two integers $n$ and $Q$, representing the number of nodes and the number of operations Youxiang performs, where nodes are numbered from $1$ to $n$.

The next $n-1$ lines each contain three integers $a, b, c$ ($1 \le c \le 1000$), representing an edge between $a$ and $b$ with weight $c$.

The next $Q$ lines each contain two integers $u, e$ ($0 \le |e| \le 1000$), representing that Youxiang has added $e$ troops at node $u$ (if $e < 0$, it means Youxiang has reduced $|e|$ troops at node $u$, which is equivalent to $d_u \leftarrow d_u + e$). It is guaranteed that the number of troops at any node is non-negative at any time.

Output

For each of Youxiang's operations, output the minimum cost after the operation is completed, assuming Youxiang chooses the optimal node for the supply station.

Constraints

• For 15% of the data: $n \le 5000, Q \le 2000$.
• For 10% of the data: $n \le 10^5, Q \le 10^5$, and the tree structure is a line.
• For 5% of the data: $n \le 10^5, Q \le 10^5$, and the tree is randomly generated (generated by choosing a random parent from nodes $i < j$ for each node $j > 1$).
• For 5% of the data: $n \le 10^5, Q \le 10^5$, and the tree structure is a cross (i.e., two lines intersecting at a common point, see the figure below).

• For 5% of the data: $n \le 10^5, Q \le 10^5$, and the tree is a complete binary tree rooted at node 1 (the definition is the same as a binary heap, which I believe everyone knows, so I won't explain it).
• For 30% of the data: $n \le 10^5, Q \le 10^5$, and Youxiang only adds troops ($e \ge 0$).
• For 30% of the data: $n \le 10^5, Q \le 10^5$.
• It is quite amazing that for all data, the degree of all nodes in this tree does not exceed 20, and $n, Q \ge 1$.

Examples

Input 1

10 5
1 2 1
2 3 1
2 4 1
1 5 1
2 6 1
2 7 1
5 8 1
7 9 1
1 10 1
3 1
2 1
8 1
3 1
4 1

Output 1

0
1
4
5
6