markdown

F. 移动电话网络

时间限制：每个测试点 $3$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

你正在管理一个移动电话网络，并希望提供有竞争力的价格来连接整个网络。
该网络共有 $n$ 个节点。

你的竞争对手已经提供了一些节点之间的连接，并给出了固定价格。这些连接是双向的。竞争对手最初提供了 $m$ 条连接。其中第 $i$ 条连接连接节点 $a_i$ 和 $b_i$，价格为 $w_i$。

你有一份包含 $k$ 条连接的清单，希望由你来提供。保证这些连接不会形成任何环。其中第 $j$ 条连接连接节点 $a_j$ 和 $b_j$。这些连接也是双向的，但它们的价格尚未确定。

你可以将这些连接的价格设置为任意整数，每条连接的价格可以独立设定。设定价格后，客户会选择恰好 $n-1$ 条连接，使得所有节点连通成一个网络，并且所选连接的总价格尽可能小。如果存在多种这样的选择，客户会任意选择其中包含你的连接数量最多的一种。

你希望设定价格，使得客户最终选择你提供的所有 $k$ 条连接，并且你所提供的连接的价格总和尽可能大。

请输出你能获得的最大利润，如果利润可以无限大，则输出 $-1$。

输入格式

第一行包含三个整数 $n$、$k$ 和 $m$（$1 \leq n, k, m \leq 5 \times 10^5$，$k \leq n-1$），分别表示节点数、你提供的连接数以及竞争对手提供的连接数。

接下来 $k$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示你提供的一条连接。保证这些连接不构成环。

接下来 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $w_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq w_i \leq 10^9$），表示竞争对手提供的一条连接及其价格。这些连接中不存在自环，且没有两条连接连接相同的节点对。此外，这些连接按价格非递减顺序给出（即对于所有合法的 $i$，有 $w_{i-1} \leq w_i$）。

注意，某些连接可能同时出现在你提供的集合和竞争对手提供的集合中（但每个集合内部不会出现重复连接）。

保证你提供的连接和竞争对手提供的连接的并集构成一个连通网络。

输出格式

输出一个整数，表示在合理设定你提供的连接价格后，你能获得的最大利润。如果利润可以无限大，则输出 $-1$。

样例

输入样例 1

4 3 6
1 2
3 4
1 3
2 3 3
3 1 4
1 2 4
4 2 8
4 3 8
4 1 10

输出样例 1

14

输入样例 2

3 2 1
1 2
2 3
1 2 30

输出样例 2

-1

输入样例 3

4 3 3
1 2
1 3
1 4
4 1 1000000000
4 2 1000000000
4 3 1000000000

输出样例 3

3000000000

说明

在第一个样例中，最优方案是将你的第 $1$ 条连接（$1-2$）定价为 $3$，第 $2$ 条连接（$3-4$）定价为 $2$，第 $3$ 条连接（$1-3$）定价为 $4$。此时最便宜的连通网络总价格为 $14$，客户会选择包含你所有连接的方案。

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