Etopika
Description
**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?
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 the minimum total distance the monkey 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.
5 2
1 2 4
2 4 3
4 3 1
5 4 1
5 3
2 5
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$.