该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

星网建设（network）

题目描述

$\text{DAMON THRONE}$ 准备建设一套训练基地通信网络。

一共有 $n$ 个训练基地，编号为 $1$ 到 $n$，其中有 $c$ 条通信线路已经建好，可以直接使用，不需要额外花费；另外还有 $m$ 条候选通信线路。第 $i$ 条候选线路连接基地 $u_i$ 和基地 $v_i$，建设费用为 $w_i$。

现在希望选择若干条候选线路进行建设，使得所有训练基地之间都能够互相通信。

请你求出完成通信网络建设所需要的最小额外费用，以及在最小费用下需要新建多少条候选线路。

如果无论如何都无法使所有基地连通，输出 $-1$。

输入格式

第一行包含三个整数 $n,m,c$，分别表示训练基地数量、候选线路数量和已经建好的线路数量。

接下来 $c$ 行，每行包含两个整数 $u,v$，表示基地 $u$ 和基地 $v$ 之间已经有一条可用线路。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示一条候选线路。

输出格式

如果无法使所有基地连通，输出一行一个整数：$-1$

否则输出一行两个整数，分别表示：

• 最小额外费用；
• 在最小额外费用下需要新建的候选线路数量。

输入输出样例 #1

输入 #1

5 6 1
1 2
1 3 4
2 3 2
2 4 7
3 4 1
4 5 3
2 5 10

输出 #1

6 3

样例解释 #1

已有线路连接了基地 $1$ 和基地 $2$。

可以新建以下候选线路：

$$3\leftrightarrow4$$

费用为 $1$；

$$2\leftrightarrow3$$

费用为 $2$；

$$4\leftrightarrow5$$

费用为 $3$。

此时所有基地连通，总费用为：

$$1+2+3=6$$

一共新建 $3$ 条线路。

输入输出样例 #2

输入 #2

4 2 0
1 2 5
3 4 6

输出 #2

-1

样例解释 #2

基地 $1,2$ 可以连通，基地 $3,4$ 可以连通，但无法让这两个连通块之间互相通信，所以输出 $-1$。

输入输出样例 #3

输入 #3

4 1 3
1 2
2 3
3 4
1 4 100

输出 #3

0 0

样例解释 #3

已有线路已经让所有基地连通，因此不需要新建任何候选线路。

数据范围与约定

对于所有测试数据，保证：

$$1 \le n \le 2\times 10^5,\quad 0 \le m,c \le 2\times 10^5 ,\quad 1 \le w_i \le 10^9 $$$$1 \le u,v,u_i,v_i \le n ,\quad u\ne v,\quad u_i\ne v_i $$

测试点	分值	$n$	$m,c$	$w_i$	特殊性质
$1\sim 2$	$10$	$\le 200$	$\le 500$	$\le 10^3$	无
$3\sim 4$	$20$	$\le 2000$	$\le 5000$	$\le 10^9$	$\text{A}$
$5\sim 6$		$\le 10^5$			$\text{B}$
$7\sim 8$		$\le 2\times10^5$			$\text{C}$
$9\sim 10$	$30$				无

特殊性质 $\text{A}$：保证 $c=0$，即没有已经建好的线路。

特殊性质 $\text{B}$：保证已有线路已经使所有基地连通。

特殊性质 $\text{C}$：保证所有候选线路费用相同。