修复 Yusland 的道路

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

Yusland 有 $n$ 个交叉口，由 $n-1$ 条双向道路连接，任意两个交叉口之间都可互相到达。以交叉口 $1$ 为根，这些道路构成一棵有根树。

镇上有 $m$ 名道路修理工。第 $i$ 名工人位于交叉口 $u_i$，收费 $c_i$，能够修复从 $u_i$ 到交叉口 $v_i$ 的简单路径上的全部道路。保证 $v_i$ 是 $u_i$ 的祖先。允许 $u_i=v_i$，此时该工人不修复任何道路。

请选择若干工人，使树上的每条道路都至少被修复一次，并最小化总费用。道路可以被重复修复。如果无法修复全部道路，输出 $-1$。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n-1$ 行，每行两个整数 $x,y$，表示一条连接交叉口 $x,y$ 的道路。

最后 $m$ 行，每行三个整数 $u_i,v_i,c_i$，描述一名工人。

输出格式

若无法修复所有道路，输出 $-1$；否则输出所需的最小总费用。

样例输入 1

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

样例输出 1

8

数据范围

对于所有数据，$1\le n,m\le300000$，$1\le x,y,u_i,v_i\le n$，$1\le c_i\le10^9$。输入道路构成一棵树，且 $v_i$ 是 $u_i$ 的祖先。