E. Space emergency
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Artemis VII Orbital Research Station consists of $$$N$$$ modules connected by $$$N-1$$$ pressurized corridors, in such a way that it is possible to travel from any module to any other by traversing the corridors. Each corridor has a length measured in meters.

Over time, engineers arrive at the station. Initially, no module contains any engineers, and a single module may host multiple engineers simultaneously. The total number of engineers in the station is always even.

In the event of an emergency, all engineers must gather into pairs. Each engineer must meet exactly one other engineer by traveling through the corridors, and every engineer must belong to exactly one pair. The cost of an emergency response is the minimum total distance that the engineers need to travel, summed over all pairs. In other words, it is the sum of the distances between the two engineers in each pair, minimized over all possible ways of forming the pairs.

You are given a sequence of $$$Q$$$ events. In each event, two new engineers arrive at the station and are assigned to modules $$$x$$$ and $$$y$$$ (not necessarily distinct). After each event, determine the cost of an emergency response considering all engineers currently present in the station.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 10^5$$$), the number of modules and the number of events.

The $$$i$$$-th of the next $$$N-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i, v_i \le N$$$, $$$u_i \ne v_i$$$, $$$1 \le w_i \le 10^9$$$), describing a corridor of length $$$w_i$$$ connecting modules $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that the corridors connect all modules; that is, there exists a path between any pair of modules.

The $$$i$$$-th of the next $$$Q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le N$$$), representing the modules to which the two new engineers arriving in the $$$i$$$-th event are assigned. The values $$$x_i$$$ and $$$y_i$$$ may be equal.

Output

Your program must print $$$Q$$$ lines. The $$$i$$$-th line should contain the cost of an emergency response after the $$$i$$$-th event.

Examples
Input
5 4
1 2 2
1 3 3
3 4 1
3 5 4
2 4
2 5
3 3
1 5
Output
6
5
5
4
Input
6 4
1 2 1
1 3 2
3 4 8
4 5 3
4 6 3
1 4
2 6
3 5
1 1
Output
10
4
15
15