题目描述

阿兔和他的兔子伙伴们居住在一个由多个兔子窝组成的兔子洞中。这个兔子洞的结构呈树形，节点代表着不同的兔子窝，边则是连接它们的通道。

每条通道有一个初始使用寿命 $z$，且每次兔子通过该通道都会减少 $1$ 点寿命。如果某次通过后该通道寿命为 $0$ 则坍塌，阿兔会立即去修复它。

通道修复的规则如下：

• 如果通道从未修复过，那么它的使用寿命会恢复到 $\lceil hp_{i}/ 2\rceil$。
• 如果通道已经修复过，使用寿命将恢复为 $\lceil prehp_{i}/ 2\rceil$（ $prehp_{i}$ 是上次修复后的寿命）。

如果你知道兔子洞的结构和兔子们的行动路径，你是否能够计算出阿兔一共修复了多少次道路呢？

输入格式

第一行包含两个正整数 $n,k \ (1\leq n,k \leq 2*10^{5})$，分别表示节点的数量和兔子行动路径的条目数。

接下来 $n-1$ 行，每行包含三个正整数 $x,y,z \ (1\leq x,y \leq n,1\leq z \leq 10^{9})$，表示节点 $x$ 到节点 $y$ 这条通道的初始使用寿命为 $z$。

接下来 $k$ 行，每行包含两个正整数 $x,y \ (1\leq x,y \leq n)$，表示一只兔子从节点 $x$ 出发，沿着简单路径抵达节点 $y$。

输出格式

输出一个整数表示阿兔一共修复了多少次道路。

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

6