F. Etopika
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

**Bobliu** the monkey lives on a banana tree. The tree can be modelled as a tree (a connected graph with $$$N$$$ nodes and $$$N-1$$$ edges). Bob is currently on the ground, marked node $$$1$$$. Every day, $$$2$$$ new nodes (not always distinct) grow a banana, and Bob climbs from his current spot to the 2 bananas (in any order) and eats them. He then takes a nap where he is and sleeps until the next day. What is the least distance he must travel?

Input

The first line contains $$$N$$$, the number of nodes, and $$$D$$$, the number of days.

The next $$$N-1$$$ lines contain $$$a$$$, $$$b$$$, and $$$c$$$, marking a branch between $$$a$$$ and $$$b$$$ of length $$$c$$$.

The next $$$D$$$ lines contain $$$x$$$ and $$$y$$$, the location of the 2 bananas that day.

## Constraints

For all subtasks:

$$$1 \le a,b,x,y \le N$$$

$$$0 \le c \le 1000$$$

$$$1 \le N \le 10^5$$$

$$$1 \le D \le 10^6$$$

### Subtask 1 [10 $$$1 \le D,N \le 10$$$

### Subtask 2 [20 $$$1 \le N \le 1000$$$

Output

Output the minimum total distance the monkey must travel.

Example
Input
5 2
1 2 4
2 4 3
4 3 1
5 4 1
5 3
2 5
Output
14
Note

On the first day, Bob starts at node $$$1$$$ and travels to node $$$3$$$ and then node $$$5$$$ to eat the bananas.

On the second day, Bob is already at node $$$5$$$ and eats the banana before travelling to node $$$2$$$.