← 返回题目列表

Codeforces · 671/D

D. 尤斯兰的道路

中文机器翻译题面 查看原题

尤斯兰市长刚刚中了彩票,并决定花钱买一些对城镇有益的东西。例如,修复镇上所有的道路。

Yusland 由 n 个交叉路口组成,由 n - 1 条双向道路连接。人们可以仅使用这些道路从任何十字路口行驶到任何其他十字路口。

镇上只有一家修路公司,名叫“RC公司”。公司中心位于1号路口。RC公司不会修你告诉他们的道路。相反,他们在一些路口有工作人员,只能修复一些特定的道路。第 i 个工人可以获得 ci 币,然后他修复从 ui 到某个 vi 的路径上的所有道路,该 vi 位于从 ui 到交叉路口 1 的路径上。

市长要求您选择最便宜的方式来雇用部分工人来修复尤斯兰的所有道路。有些道路可以多次维修。

如果无法修复所有道路,则打印 - 1。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 300 000) - 分别是 Yusland 的城市数量和工人数量。

然后沿着 n−1 行,每行包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ n) — 第 i 条路连接的交叉口索引。

最后m行提供了工人的描述,每行包含三个整数ui,vi和ci(1≤ui,vi≤n,1≤ci≤109)。这意味着第i个工人可以花费ci币修复从vi到ui路径上的所有道路。保证 vi 位于从 ui 到 1 的路径上。注意 vi 和 ui 可能重合。

输出

如果不可能修复所有道路,则打印 - 1。否则打印一个整数 - 使用“RC 公司”工人修复所有道路所需的最低成本。

示例

输入 #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、3、4、5的工人,有些道路会被修复多次,但没关系。成本将等于 2 + 3 + 1 + 2 = 8 个硬币。