Score : $600$ points

Problem Statement

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$ has a 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.

Constraints

• $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$
• The given graph is a forest.
• All input values are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

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

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_M$ $y_M$

Output

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

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

7

If we connect vertices $0$ and $5$, the graph becomes connected, for the cost of $1 + 6 = 7$ dollars.

5 0
3 1 4 1 5

Impossible

We can't make the graph connected.

1 0
5

0

The graph is already connected, so we do not need to add any edges.