CF1255B.Fridge Lockers

Hanh lives in a shared apartment. There are $n$ people (including Hanh) living there, each has a private fridge.

$n$ fridges are secured by several steel chains. Each steel chain connects two different fridges and is protected by a digital lock. The owner of a fridge knows passcodes of all chains connected to it. A fridge can be open only if all chains connected to it are unlocked. For example, if a fridge has no chains connected to it at all, then any of $n$ people can open it.

For exampe, in the picture there are $n=4$ people and $5$ chains. The first person knows passcodes of two chains: $1-4$ and $1-2$. The fridge $1$ can be open by its owner (the person $1$), also two people $2$ and $4$ (acting together) can open it.

The weights of these fridges are $a_1, a_2, \ldots, a_n$. To make a steel chain connecting fridges $u$ and $v$, you have to pay $a_u + a_v$ dollars. Note that the landlord allows you to create multiple chains connecting the same pair of fridges.

Hanh's apartment landlord asks you to create exactly $m$ steel chains so that all fridges are private. A fridge is private if and only if, among $n$ people living in the apartment, only the owner can open it (i.e. no other person acting alone can do it). In other words, the fridge $i$ is not private if there exists the person $j$ ($i \ne j$) that the person $j$ can open the fridge $i$.

For example, in the picture all the fridges are private. On the other hand, if there are $n=2$ fridges and only one chain (which connects them) then both fridges are not private (both fridges can be open not only by its owner but also by another person).

Of course, the landlord wants to minimize the total cost of all steel chains to fulfill his request. Determine whether there exists any way to make exactly $m$ chains, and if yes, output any solution that minimizes the total cost.

韩生活在一间合租公寓中。公寓里共有 $n$ 人（包括韩），每人拥有一台私人的冰箱。

这 $n$ 台冰箱由若干条钢链连接并加固。每条钢链连接两台不同的冰箱，并由一个数字锁保护。某台冰箱的主人知晓所有与该冰箱相连的钢链的密码。一台冰箱仅当所有与之相连的钢链均被解锁时，才能被打开。例如，若某台冰箱没有任何钢链与其相连，则公寓中的任意一人（共 $n$ 人）均可将其打开。

例如，图中 $n=4$ 人，共 $5$ 条钢链。第一个人知晓两条钢链的密码：$1$–$4$ 和 $1$–$2$。冰箱 $1$ 可由其主人（即第 $1$ 个人）打开；此外，第 $2$ 人与第 $4$ 人合作（共同提供各自掌握的密码）也可将其打开。

这些冰箱的重量分别为 $a_1, a_2, \ldots, a_n$。要制作一条连接冰箱 $u$ 和 $v$ 的钢链，需花费 $a_u + a_v$ 美元。注意：房东允许你在同一对冰箱之间创建多条钢链。

韩的公寓房东要求你恰好制作 $m$ 条钢链，使得所有冰箱均为私有的。一台冰箱是私有的，当且仅当在公寓居住的 $n$ 人中，仅有其主人能单独打开它（即其他任何人单独行动均无法打开）。换言之，冰箱 $i$ 不是私有的，当且仅当存在某人 $j$（$j \ne i$），使得第 $j$ 个人能单独打开冰箱 $i$。

例如，在上图中，所有冰箱都是私有的。另一方面，若 $n = 2$，且仅有一条钢链（连接这两台冰箱），则两台冰箱均不是私有的（因为每台冰箱不仅能被其主人打开，也能被另一人单独打开）。

当然，房东希望总成本最小化，以满足上述要求。请判断是否存在一种方案，能恰好制作 $m$ 条钢链；若存在，请输出任意一种使总成本最小的方案。

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 10$). Then the descriptions of the test cases follow.

The first line of each test case contains two integers $n$, $m$ ($2 \le n \le 1000$, $1 \le m \le n$) — the number of people living in Hanh's apartment and the number of steel chains that the landlord requires, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^4$) — weights of all fridges.

每个测试包含多个测试用例。第一行包含测试用例的数量 $T$（$1 \le T \le 10$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$、$m$（$2 \le n \le 1000$，$1 \le m \le n$）—— 分别表示住在Hanh公寓中的人数以及房东要求的钢链数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^4$）—— 表示所有冰箱的重量。

For each test case:

• If there is no solution, print a single integer $-1$.
• Otherwise, print a single integer $c$ — the minimum total cost. The $i$-th of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), meaning that the $i$-th steel chain connects fridges $u_i$ and $v_i$. An arbitrary number of chains can be between a pair of fridges.

If there are multiple answers, print any.

对于每个测试用例：

• 如果无解，输出单个整数 $-1$。
• 否则，输出单个整数 $c$ —— 最小总成本。接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示第 $i$ 条钢链连接冰箱 $u_i$ 和 $v_i$。任意一对冰箱之间可以有任意数量的钢链。

如有多个答案，输出任意一个即可。