CF1023F.Mobile Phone Network

You are managing a mobile phone network, and want to offer competitive prices to connect a network.

The network has $n$ nodes.

Your competitor has already offered some connections between some nodes, with some fixed prices. These connections are bidirectional. There are initially $m$ connections the competitor is offering. The $i$-th connection your competitor is offering will connect nodes $fa_i$ and $fb_i$ and costs $fw_i$.

You have a list of $k$ connections that you want to offer. It is guaranteed that this set of connection does not form any cycle. The $j$-th of these connections will connect nodes $ga_j$ and $gb_j$. These connections are also bidirectional. The cost of these connections have not been decided yet.

You can set the prices of these connections to any arbitrary integer value. These prices are set independently for each connection. After setting the prices, the customer will choose such $n - 1$ connections that all nodes are connected in a single network and the total cost of chosen connections is minimum possible. If there are multiple ways to choose such networks, the customer will choose an arbitrary one that also maximizes the number of your connections in it.

You want to set prices in such a way such that all your $k$ connections are chosen by the customer, and the sum of prices of your connections is maximized.

Print the maximum profit you can achieve, or $-1$ if it is unbounded.

你正在运营一个手机网络，希望提供有竞争力的价格来连接整个网络。

该网络包含 $n$ 个节点。

你的竞争对手已预先提供了一些节点之间的连接，并设定了固定价格。这些连接是双向的。初始时，竞争对手共提供了 $m$ 条连接。其中第 $i$ 条连接连接节点 $fa_i$ 和 $fb_i$，费用为 $fw_i$。

你手头还有一份共 $k$ 条你打算提供的连接列表。保证这些连接本身不构成任何环。其中第 $j$ 条连接连接节点 $ga_j$ 和 $gb_j$，同样是双向的。这些连接的费用尚未确定。

你可以将每条连接的费用设定为任意整数（各连接独立设定）。设定完所有费用后，客户将从中选择恰好 $n - 1$ 条连接，使得全部 $n$ 个节点连通成一棵树，且所选连接的总费用最小。若存在多种总费用相同的方案，客户将在所有总费用最小的方案中，任意选择一个包含你提供的连接数量最多的方案。

你希望设定费用，使得客户最终所选的树恰好包含你全部 $k$ 条连接，并且你这 $k$ 条连接的总费用之和尽可能大。

请输出你能获得的最大总利润；若该最大值无上界，则输出 $-1$。

The first line of input will contain three integers $n$, $k$ and $m$ ($1 \leq n, k, m \leq 5 \cdot 10^5, k \leq n-1$), the number of nodes, the number of your connections, and the number of competitor connections, respectively.

The next $k$ lines contain two integers $ga_i$ and $gb_i$ ($1 \leq ga_i, gb_i \leq n$, $ga_i \not= gb_i$), representing one of your connections between nodes $ga_i$ and $gb_i$. Your set of connections is guaranteed to be acyclic.

The next $m$ lines contain three integers each, $fa_i$, $fb_i$ and $fw_i$ ($1 \leq fa_i, fb_i \leq n$, $fa_i \not= fb_i$, $1 \leq fw_i \leq 10^9$), denoting one of your competitor's connections between nodes $fa_i$ and $fb_i$ with cost $fw_i$. None of these connections connects a node to itself, and no pair of these connections connect the same pair of nodes. In addition, these connections are given by non-decreasing order of cost (that is, $fw_{i-1} \leq fw_i$ for all valid $i$).

Note that there may be some connections that appear in both your set and your competitor's set (though no connection will appear twice in one of this sets).

It is guaranteed that the union of all of your connections and your competitor's connections form a connected network.

输入的第一行包含三个整数 $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 \neq gb_i$），表示你的一条连接，其两端节点为 $ga_i$ 和 $gb_i$。保证你的所有连接构成一个无环图（即森林）。

接下来的 $m$ 行每行包含三个整数 $fa_i$、$fb_i$ 和 $fw_i$（$1 \leq fa_i, fb_i \leq n$，$fa_i \neq fb_i$，且 $1 \leq fw_i \leq 10^9$），表示竞争对手的一条连接，其两端节点为 $fa_i$ 和 $fb_i$，代价为 $fw_i$。这些连接均不连接节点到自身，且任意两条连接不会连接完全相同的节点对。此外，这些连接按代价非递减顺序给出（即对所有合法的 $i$，均有 $fw_{i-1} \leq fw_i$）。

注意：可能存在某些连接同时出现在你的连接集合与竞争对手的连接集合中（但任一集合内部不会出现重复连接）。

保证你与竞争对手的所有连接的并集构成一个连通网络。

Print a single integer, the maximum possible profit you can achieve if you set the prices on your connections appropriately. If the profit is unbounded, print $-1$.

输出一个整数，表示若你恰当地设定各连接的价格，所能获得的最大可能利润。如果利润无上界，则输出 $-1$。

In the first sample, it's optimal to give connection $1-3$ cost $3$, connection $1-2$ cost $3$, and connection $3-4$ cost $8$. In this case, the cheapest connected network has cost $14$, and the customer will choose one that chooses all of your connections.

In the second sample, as long as your first connection costs $30$ or less, the customer chooses both your connections no matter what is the cost of the second connection, so you can get unbounded profit in this case.

在第一个样例中，最优策略是将连接 $1-3$ 的费用设为 $3$，连接 $1-2$ 的费用设为 $3$，连接 $3-4$ 的费用设为 $8$。此时，最便宜的连通网络总费用为 $14$，客户将选择包含你所有连接的方案。

在第二个样例中，只要你的第一条连接费用不超过 $30$，无论第二条连接的费用是多少，客户都会选择你的两条连接，因此在此情况下你可以获得无界的利润。