markdown

D. 尤斯兰德的公路

尤斯兰德的市长刚刚中了彩票，决定把钱花在有益于城镇的事情上，比如修复镇上的所有道路。

尤斯兰德由 $n$ 个路口组成，这些路口之间由 $n-1$ 条双向道路连接。利用这些道路，可以从任意一个路口到达任意另一个路口。

镇上只有一家道路修复公司，名为“RC 公司”。公司的中心位于 $1$ 号路口。RC 公司不会按照你指定的道路进行修复。相反，他们在某些路口有工人，这些工人只能修复某些特定的路径。第 $i$ 个工人可以被支付 $c_i$ 枚金币，然后他会修复从 $u_i$ 到某个 $v_i$ 之间的所有道路，其中 $v_i$ 位于从 $u_i$ 到 $1$ 号路口的路径上。

市长请你选择最便宜的方式雇佣一部分工人，以便修复尤斯兰德的所有道路。允许某些道路被修复多次。

如果无法修复所有道路，则输出 $-1$。

输入

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 300\,000$）—— 分别表示尤斯兰德的路口数量和工人数量。

接下来 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$）—— 表示第 $i$ 条道路连接的两个路口编号。

最后 $m$ 行是对工人的描述，每行包含三个整数 $u_i$、$v_i$ 和 $c_i$（$1 \le u_i, v_i \le n$，$1 \le c_i \le 10^9$）。这意味着第 $i$ 个工人可以用 $c_i$ 枚金币修复从 $v_i$ 到 $u_i$ 路径上的所有道路。保证 $v_i$ 位于从 $u_i$ 到 $1$ 的路径上。注意 $v_i$ 和 $u_i$ 可能重合。

输出

如果无法修复所有道路，则输出 $-1$。否则输出一个整数 —— 使用“RC 公司”工人修复所有道路所需的最小花费。

样例

输入

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

输出

8

说明

在第一个样例中，我们应该选择编号为 $1$、$3$、$4$ 和 $5$ 的工人，有些道路会被修复多次，但这是允许的。总花费为 $2 + 3 + 1 + 2 = 8$ 枚金币。