BThero 需要从一个迷宫中逃脱，该迷宫由一棵具有 $n$ 个顶点和 $n-1$ 条边的树表示，每条边都有其特定的长度。此外，迷宫的顶点中包含 $2m$ 瓶毒药：每种 $m$ 种毒药各两瓶。

当 BThero 第一次进入一个顶点时，他会立即喝掉该顶点内的所有毒药。当他再次到达一个曾经去过的顶点时，那里已经没有毒药可喝了。

当 BThero 喝下一瓶他尚未喝过的某种毒药时，他会中该种毒药的毒。为了解毒，BThero 必须找到并喝下同一类型的另一瓶毒药。

BThero 从顶点 $s$ 开始他的路径，并在该顶点立即喝掉所有毒药。然后，他经过一些顶点，直到他不再中毒，之后他返回顶点 $s$ 并离开迷宫。

我们需要找到一个起始顶点 $s$，使得如果 BThero 从该顶点开始他的路径，在选择最优路线的情况下，他需要行进的总距离最小。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$)：迷宫中的顶点数和毒药种类数。

接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^9$)，描述了顶点 $u_i$ 和 $v_i$ 之间长度为 $w_i$ 的双向边。

接下来的 $m$ 行，每行包含两个整数 $a_j$ 和 $b_j$ ($1 \le a_j, b_j \le n$)：存放第 $j$ 种毒药的两瓶毒药所在的顶点。注意，可能存在 $a_j = b_j$ 的情况，在这种情况下，进入该顶点时，BThero 会中毒并立即解毒。

输出格式

输出一行，包含一个整数：如果从最优顶点开始，BThero 为解除所有毒药所需要行进的最小距离。

样例

输入 1

4 2
1 2 1
1 3 10
1 4 100
1 3
2 4

输出 1

20

输入 2

5 2
1 2 1
1 3 10
1 4 100
1 5 1000
1 3
2 4

输出 2

0

输入 3

7 4
1 2 8
1 3 9
2 4 10
2 5 11
3 6 12
3 7 13
2 3
7 6
2 1
4 5

输出 3

34