問題文

$N$ 頂点 $M$ 辺からなる無向グラフがあります。 各頂点は $1$ から $N$ の、各辺は $1$ から $M$ の整数で番号づけられており、 $1\le i \le M$について、辺 $i$ は頂点 $u_i$ と頂点 $v_i$ とを双方向に結んでいます。 また、各頂点は非負整数の重みを持ち、 $1\le i\le N$ について、頂点 $i$ の重みは $A_i$ です。

最初、 どの頂点も黒く塗られていません。ここで、以下のような操作を考えます。

• $2$ 頂点の組 $(u,v)$ であって、どちらも黒く塗られておらず、かつ直接辺で結ばれているようなものを $1$ つ選ぶ。 $u$ を黒く塗り、 $A_v$ 円を得る。

各辺は無向辺であることから、組 $(u,v)$ に対して操作が可能であるとき、組 $(v,u)$ に対しても操作が可能であることに注意してください。

この操作を $0$ 回以上、好きな回数行うことによって得られる金額の総和としてあり得る最大値は何円ですか？

$T$ 個のテストケースについて答えてください。

制約

• $1\le T\le 2\times 10^5$
• $1\le N\le 2\times 10^5$
• $0\le M\le 2\times 10^5$
• $1\le u_i < v_i\le N\ (1\le i\le M)$
• $(u_i,v_i) \neq (u_j,v_j)\ (1\le i < j\le M)$
• $0\le A_i\le 10^9\ (1\le i\le N)$
• $T$ 個のテストケースにわたる $N$ の総和と $M$ の総和はそれぞれ $2\times 10^5$ 以下
• 入力は全て整数

入力

入力は以下の形式で与えられます。ここで、$case_i$ は $i$ 番目のテストケースを表します。

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各テストケースは次の形式で与えられます。

$N\ M$
$A_1\ A_2\ \cdots\ A_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

出力

$T$ 行出力してください。 $i$ 行目には、 $i$ 番目のテストケースについての答えを出力してください。

サンプル

2
6 7
7 2 3 1 3 6
1 2
1 3
2 4
3 4
3 5
4 6
5 6
10 13
4 9 0 6 7 1 5 9 3 7
1 6
1 7
1 9
2 4
2 9
3 7
3 9
5 10
6 7
6 8
6 9
8 9
9 10

26
52