已有边的稠密网络

难度：T2

【知识点：Prim最小生成树】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

已有无向线路不再收费，可以购买候选线路补齐网络。求使所有顶点连通所需的最少新增费用。

输入格式

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$；$m$ 为随后给出的带权边条数。每条带权边独占一行，依次为 $u,v,w$，表示从 $u$ 到 $v$ 的边及权值 $w$；无向边可双向通行，有向边只能从 $u$ 到 $v$ 通行。 已建免费线路先输入，共 $k$ 行，每行只有两个端点 $u,v$。

输入$n$、$k$、$m$；$k$条已建无向边$u$、$v$；$m$条候选边$u$、$v$、$w$。已有边不再收费，可与候选边重叠。

输出格式

输出最小新增连通费用，不可行输出IMPOSSIBLE。

数据范围

$1\le n\le 500$，$0\le k,m\le 200000$，$0\le w\le 10^9$，端点在$1$..$n$。

样例输入

1 0 0

样例输出

0

样例输入 2

4 1 3
1 2
2 3 4
3 4 2
1 4 10

样例输出 2

6

样例说明 2

免费线路不收费，再选两条费用为 $4,2$ 的线路即可。