CF1023F Mobile Phone Network

你正在管理一个移动电话网络，并希望为连接网络提供有竞争力的价格。 该网络有 $n$ 个节点。 你的竞争对手已经为部分节点之间提供了一些连接，并设定了固定的价格。这些连接是双向的。最初有 $m$ 条由竞争对手提供的连接。第 $i$ 条连接连接节点 $fa_i$ 和 $fb_i$，费用为 $fw_i$。 你有一份包含 $k$ 条你想要提供的连接的列表。保证这 $k$ 条连接不会形成环。第 $j$ 条连接将连接节点 $ga_j$ 和 $gb_j$。这些连接同样是双向的。这些连接的费用尚未决定。 你可以为这些连接设置任意整数价格。每条连接的价格可以独立设置。设置好价格后，客户会选择 $n-1$ 条连接，使得所有节点连通且总费用最小。如果有多种选择方式，客户会选择其中包含你最多连接数的方案。 你希望设置价格，使得客户选择你所有的 $k$ 条连接，并且你这些连接的价格之和最大。 请输出你能获得的最大利润。如果利润无上界，请输出 $-1$。

输入的第一行包含三个整数 $n$、$k$ 和 $m$（$1 \leq n, k, m \leq 5 \cdot 10^5, k \leq n-1$），分别表示节点数、你的连接数和竞争对手的连接数。 接下来的 $k$ 行，每行包含两个整数 $ga_i$ 和 $gb_i$（$1 \leq ga_i, gb_i \leq n$，$ga_i \not= gb_i$），表示你的一条连接。保证你的所有连接不会形成环。 接下来的 $m$ 行，每行包含三个整数 $fa_i$、$fb_i$ 和 $fw_i$（$1 \leq fa_i, fb_i \leq n$，$fa_i \not= fb_i$，$1 \leq fw_i \leq 10^9$），表示竞争对手的一条连接及其费用。这些连接不会连接自身，且任意一对节点之间至多有一条竞争对手的连接。这些连接按费用非递减顺序给出（即 $fw_{i-1} \leq fw_i$）。 注意，某些连接可能同时出现在你的集合和竞争对手的集合中（但在同一个集合中不会重复出现）。 保证你和竞争对手所有连接的并集能够使整个网络连通。

输出一个整数，表示你能获得的最大利润。如果利润无上界，输出 $-1$。

在第一个样例中，最优做法是将连接 $1-3$ 的费用设为 $3$，连接 $1-2$ 的费用设为 $3$，连接 $3-4$ 的费用设为 $8$。此时，最便宜的连通网络费用为 $14$，且客户会选择包含你所有连接的方案。 在第二个样例中，只要你的第一条连接费用不超过 $30$，客户无论如何都会选择你的两条连接，因此你可以让第二条连接的费用任意大，所以利润无上界。 由 ChatGPT 4.1 翻译