CF671D Roads in Yusland

Yusland 的市长刚刚中了大奖，决定把奖金花在为城镇做一件好事，比如修复镇上所有的道路。 Yusland 由 $n$ 个交叉口组成，通过 $n-1$ 条双向道路连接。仅通过这些道路，可以从任意一个交叉口到达另一个交叉口。 镇上只有一个道路修理公司“RC company”。公司的总部设在交叉口 $1$。RC company 不会按你的要求修路，反而是他们在某些交叉口有工人，每个工人只能修复特定的一些路径。第 $i$ 个工人收取 $c_i$ 枚金币，能修复从 $u_i$ 到某个 $v_i$（$v_i$ 必定在 $u_i$ 到交叉口 $1$ 的路径上）路径上的所有道路。 市长希望你选择一些工人，使得能用最少的金币修好 Yusland 上的所有道路。允许某些道路被重复修复。 如果无法修好所有道路，请输出 $-1$。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 300000$）——Yusland 的交叉口数量及工人数。 接下来的 $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$。否则输出修好全部道路所需的最小总金币数。

在第一个样例中，应选择第 $1$、$3$、$4$ 和 $5$ 个工人，有些道路将被多次修复，这没有问题。代价为 $2+3+1+2=8$ 枚金币。 由 ChatGPT 5 翻译