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 Specification

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.

Output Specification

Output the minimum total distance the monkey must travel.

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~

Sample Input

5 2
1 2 4
2 4 3
4 3 1
5 4 1
5 3
2 5

Sample Output

14

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~.