숲 연결하기

$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$ $\ldots$ $a_{N-1}$

$x_1$ $y_1$

$\ldots$

$x_M$ $y_M$

숲을 연결된 그래프로 만드는 데 필요한 최소 총비용을 출력하라. 불가능하면 "Impossible"을 출력하라.

$1 \le N \le 100\,000$, $0 \le M \le N-1$, $1 \le a_i \le 10^9$, $0 \le x_i,y_i \le N-1$. 주어진 그래프는 숲이다. 모든 입력값은 정수이다.

예제 1에서 정점 $0$과 $5$를 연결하면 그래프가 연결되고, 비용은 $1 + 6 = 7$이다.

예제 2에서는 그래프를 연결할 수 없다.

예제 3에서는 아무것도 하지 않아도 그래프가 연결되어 있다.