19279번 - Forest Task 다국어

문제

You are given a forest with $N$ vertices and $M$ edges. The vertices are numbered 0ドル$ through $N-1$. The edges are given in the format $(x_i,y_i),ドル which means that vertex $x_i$ and $y_i$ are connected by an edge.

Each vertex $i$ is assigned value $a_i$. You want to add edges in the given forest so that the forest becomes connected. To add an edge, you choose two different vertices $i$ and $j,ドル then span an edge between $i$ and $j$. This operation costs $a_i + a_j$ dollars, and afterward neither vertex $i$ nor $j$ can be selected again.

Find the minimum total cost required to make the forest connected, or print "Impossible" if it is impossible.

입력

Input is given in the following format:

$N$ $M$

$a_0$ $a_1$ $\ldots$ $a_{N-1}$

$x_1$ $y_1$

$\ldots$

$x_M$ $y_M$

출력

Print the minimum total cost required to make the forest connected, or print "Impossible" if it is 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$. The given graph is a forest. All input values are integers.

힌트

In Sample 1, if we connect vertices 0ドル$ and 5ドル,ドル the graph become connected, and the cost is 1ドル + 6 = 7$.

In Sample 2, we can't make the graph connected.

In Sample 3, the graph is connected, regardless of whether we do something or not.