题目描述

$N$ 頂点 $M$ 辺の森が与えられます。頂点には $0$ から $N-1$ の番号がついています。 辺は $(x_i,y_i)$ の形で与えられます。これは頂点 $x_i$ と $y_i$ が辺でつながっていることを意味します。

各頂点 $i$ には $a_i$ という値が定まっています。 あなたは与えられた森に辺を追加して連結にしたいです。 辺を追加するときには、まず異なる頂点二つを選択し( $i$ , $j$ とする)、 $i$ と $j$ の間に辺を張ります。 この時コストが $a_i+a_j$ かかります。そしてこれ以降，頂点 $i$ と $j$ は永遠に選択できなくなります。

森を連結にする最小コストを求めてください。 連結にするのが不可能な場合はImpossibleと出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_0$ $a_1$ $..$ $a_{N-1}$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

输出格式

森を連結にする最小コストを出力せよ。ただし、不可能な場合はImpossibleと出力せよ。

题目大意

给你一个有$N$个顶点和$M$个边的森林，每个点有一个值$a_i$。在给定的森林中添加边$(i,j)$，森林变得连通，此操作花费$a_i+ a_j$美元，并且之后不能再选择点$i$和$j$。

第一行输入$N$，$M$；第二行输入$N$个数，表示$a_i$；然后依次输入$M$对数，表示这两个点联通。

找到连接森林所需的最低总成本，否则输出"Impossible"。

7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

7

5 0
3 1 4 1 5

Impossible

1 0
5

0

提示

制約

• $1\ <\ =\ N\ <\ =\ 100,000$
• $0\ <\ =\ M\ <\ =\ N-1$
• $1\ <\ =\ a_i\ <\ =\ 10^9$
• $0\ <\ =\ x_i,y_i\ <\ =\ N-1$
• 与えられるグラフは森
• 入力は全て整数

Sample Explanation 1

頂点 $0$, $5$ をつなぐとグラフが連結になり，この時かかるコストは $1\ +\ 6\ =\ 7$ です。

Sample Explanation 2

どのように辺を追加してもグラフを連結にすることはできません。

Sample Explanation 3

最初からグラフは連結であるので，辺を追加する必要はありません。