You are given a tree. There are n vertices and n-1 edges. There is a non-negative weight for each edge in the tree. Every time, you can select two different vertices u, v, and subtract the weight of each edge on the path by 1. You want to make the weight of all edges become zero.
What is the minimum number of operations?
You also need to support modification of edge weights: Change the weight of p-th edge to w. You need to output the answer after each modification.

The first line contains two integers .
In the following n-1 lines, each line contains three integers  - an edge (u,v) with weight w. Edges are indexed from 1 to n-1 in the order.
In the following q lines, each line contains two integers .

Output q+1 integers, the answer of the original tree and answers after each modification.

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

8
12
10
10