MST Problem

题号：NC302354
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯拿到了一个由 $n$ 个点、 $\tfrac{n \times (n-1)}{2}$ 条边组成的无向完全图，没有重边和自环，其中第 $i$ 个点的点权为 $a_i$ 。 $u,v$ 两点之间的边权为 $a_u+a_v$ 。

$\hspace{15pt}$ 而调皮的小红删除掉了其中一些边，导致图不再是一个完全图，具体来讲有 $m$ 条删除记录，第 $j$ 条记录由一个点对 $(u_j,v_j)$ 组成，表示小红删除了这条边。注意，记录可能有重复，即可能存在两条记录删除的边是一样的。

$\hspace{15pt}$ 现在你的任务就是求出这张图的最小生成树的权重（树中所有边的权重之和最小）。如果此时图不存在最小生成树，则输出 $-1$ 。

【名词解释】
$\hspace{15pt}$ 最小生成树：对于一张由 $n$ 个节点构成的连通图，选出 $n-1$ 条边将所有节点连通，且使得这 $n-1$ 条边的权重之和最小，这样的结构称为最小生成树。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示图的节点个数、小红删除边的记录条数。
第二行输入  个整数 ，表示每个节点的点权。
接下来  行，第  行输入两个正整数 ，描述第  条删除记录。

除此之外，保证单个测试文件的  之和、 之和均不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，如果此时图存在最小生成树，则输出整张图的最小生成树的权重；否则直接输出 。

示例1

输入

复制

输出

复制

7
12
-1

说明

对于第一组测试数据，整个图已经被删成一棵树，因此图自己就是自己的唯一生成树，当然也就是最小生成树，仅剩的两条边  和  的权分别为：，因此最小生成树权重为 。