配点 : $600$ 点

問題文

$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と出力してください。

制約

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

入力

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

$N$ $M$

$a_0$ $a_1$ $..$ $a_{N-1}$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_M$ $y_M$

出力

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

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

7

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

5 0
3 1 4 1 5

Impossible

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

1 0
5

0

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