CF671D.Roads in Yusland

Mayor of Yusland just won the lottery and decided to spent money on something good for town. For example, repair all the roads in the town.

Yusland consists of n intersections connected by n - 1 bidirectional roads. One can travel from any intersection to any other intersection using only these roads.

There is only one road repairing company in town, named "RC company". Company's center is located at the intersection 1. RC company doesn't repair roads you tell them. Instead, they have workers at some intersections, who can repair only some specific paths. The i-th worker can be paid c__i coins and then he repairs all roads on a path from u__i to some v__i that lies on the path from u__i to intersection 1.

Mayor asks you to choose the cheapest way to hire some subset of workers in order to repair all the roads in Yusland. It's allowed that some roads will be repaired more than once.

If it's impossible to repair all roads print  - 1.

尤斯兰德市市长刚刚中了彩票，决定将这笔钱用于为城镇做些好事，例如修复城镇中的所有道路。

尤斯兰德由 $n$ 个交叉路口组成，这些交叉路口通过 $n-1$ 条双向道路相连。仅通过这些道路，人们可以从任意一个交叉路口到达其他任意一个交叉路口。

镇上只有一家道路维修公司，名为“RC 公司”。该公司的总部位于交叉路口 1。RC 公司并不会按照您的指令去维修道路；相反，他们在某些交叉路口配备了工人，而每位工人只能维修某条特定路径上的所有道路。第 $i$ 位工人需支付 $c_i$ 枚金币，之后他将维修从 $u_i$ 到某个 $v_i$ 的整条路径上的所有道路，其中 $v_i$ 必须位于从 $u_i$ 到交叉路口 1 的路径上。

市长请您选择一种最便宜的方式，雇佣某个工人子集，使得尤斯兰德的所有道路均被修复（允许同一条道路被多次维修）。

若无法修复所有道路，请输出 $-1$。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300 000) — the number of cities in Yusland and the number of workers respectively.

Then follow _n_−1 line, each of them contains two integers x__i and y__i (1 ≤ x__i, y__i ≤ n) — indices of intersections connected by the i-th road.

Last m lines provide the description of workers, each line containing three integers u__i, v__i and c__i (1 ≤ u__i, v__i ≤ n, 1 ≤ c__i ≤ 109). This means that the i-th worker can repair all roads on the path from v__i to u__i for c__i coins. It's guaranteed that v__i lies on the path from u__i to 1. Note that v__i and u__i may coincide.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 300\,000$），分别表示 Yusland 国家的城市数量和工人的数量。

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

最后的 $m$ 行描述了工人信息，每行包含三个整数 $u_i$、$v_i$ 和 $c_i$（$1 \leq u_i, v_i \leq n$，$1 \leq c_i \leq 10^9$）。这表示第 $i$ 个工人可以花费 $c_i$ 枚金币修复从 $v_i$ 到 $u_i$ 的路径上的所有道路。保证 $v_i$ 位于从 $u_i$ 到节点 $1$ 的路径上。注意，$v_i$ 和 $u_i$ 可能重合。

If it's impossible to repair all roads then print  - 1. Otherwise print a single integer — minimum cost required to repair all roads using "RC company" workers.

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

In the first sample, we should choose workers with indices 1, 3, 4 and 5, some roads will be repaired more than once but it is OK. The cost will be equal to 2 + 3 + 1 + 2 = 8 coins.

在第一个样例中，我们应该选择索引为 1、3、4 和 5 的工人，某些道路可能会被多次修复，但这是允许的。总成本将等于 $2 + 3 + 1 + 2 = 8$ 枚金币。