Problem:
 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 ≤ N ≤ 100,000  0 ≤ M ≤ N-1  1 ≤ a_i ≤ 10^9  0 ≤ x_i,y_i ≤ 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.        Sample Input 1 7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6      Sample Output 1 7  If we connect vertices 0 and 5 , the graph becomes connected, for the cost of 1 + 6 = 7 dollars.       Sample Input 2 5 0
3 1 4 1 5      Sample Output 2 Impossible  We can't make the graph connected.       Sample Input 3 1 0
5      Sample Output 3 0  The graph is already connected, so we do not need to add any edges.

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(m)]

V = [0] * (n)


M = [[] for i in range(n)]
for i in range(m):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])


BB = []
one = 0
for ii in range(n):
    B = []
    if V[ii] == 0:
        Q = [ii]
        s = 0
        V[ii] = 1
        onef = 1
        B.append([ii,A[ii]])
        while s < len(Q):
            i = Q[s]
            for x in M[i]:
                if V[x] == 0:
                    V[x] = 1
                    onef = 0
                    B.append([x,A[x]])
                    
                    Q.append(x)
            s += 1
        if onef == 1:
            one += 1
        B.sort(key=lambda x:x[1])
        BB.append(B[0])

if len(BB) == 1:
    print(0)
elif (len(BB)-1)*2 > n:
    print("Impossible")
else:
    ans = sum([i[1] for i in BB])
    
    anoBind = [0] * n
    anoB = []
    for i in range(len(BB)):
        anoBind[BB[i][0]] = 1
    for i in range(n):
        if anoBind[i] == 0:
            anoB.append(A[i])
    anoB.sort()
    
    ans += sum(anoB[:len(BB)-2])
    print(ans)

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)





class Unionfind:

  def __init__(s,n):
    s.sz = [1] * n
    s.ances = [i for i in range(n)]

  def root(s,x):
    a = []
    y = x
    while s.ances[y] != y:
      a.append(y)
      y = s.ances[y]
    for z in a:
      s.ances[z] = y
    return y

  def conn(s,x,y):
    i = s.root(x)
    j = s.root(y)
    if i==j:
      return
    
    k  = j if (s.sz[i]<s.sz[j]) else i
    if k==j:
      s.ances[i] = j
    else:
      s.ances[j] = i
    s.sz[k] = s.sz[i] + s.sz[j]



n,m = inm()
a = inl()
nouse = 2*m-n+2
if n-m==1:
    print('0')
    exit()
if nouse<0:
    print('Impossible')
    exit()
uf = Unionfind(n)
for i in range(m):
    x,y = inm()
    uf.conn(x,y)
g = {}
for i in range(n):
    r = uf.root(i)
    if r not in g:
        g[r] = []
    g[r].append((a[i],i))

import heapq
h = []
for r in g:
    if len(g[r])<=1:
        continue
    g[r].sort()
    x,i = g[r].pop()
    heapq.heappush(h,(-x,r))
sm = 0
for i in range(nouse):
    xm,r = heapq.heappop(h)
    sm -= xm
    if len(g[r])>1:
        y,j = g[r].pop()
        heapq.heappush(h,(-y,r))
print(sum(a)-sm)

Solution (Python):
n,m,*L=map(int,open(0).read().split())
a=L[:n];b=L[n:]
if n//2+m<n-1:
	print('Impossible')
	exit()
if n-1==m:
	print(0)
	exit()
con=[[] for _ in range(n)]
vis=[0]*n
for x,y in zip(*[iter(b)]*2):
	con[x].append(y)
	con[y].append(x)
least=[]
rest=[]
cnt=0
for i in range(n):
	if not vis[i]:
		cnt+=1
		q=[i]
		es=[a[i]]
		vis[i]=1
		while q:
			cur=q.pop()
			for nxt in con[cur]:
				if not vis[nxt]:
					q.append(nxt)
					es.append(a[nxt])
					vis[nxt]=1
		mi=min(es)
		es.remove(mi)
		least.append(mi)
		rest+=es

print(sum(least+sorted(rest)[:2*(n-1-m)-cnt]))

Solution (Python):
import sys
from collections import deque, defaultdict
import heapq

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()


def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    
    A[by] = bx

edges = [[] for _ in range(N)]
V = [i for i in range(N)]
for _ in range(M):
    x, y = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)
    edges[x].append(y)
    edges[y].append(x)

for i in range(N):
    V[i] = find(V, i)

if M == N - 1:
    print(0); exit()
elif N < 2 * (N-M-1):
    print('Impossible'); exit()

root_point = defaultdict(list)
for i in range(N):
    r = V[i]
    heapq.heappush(root_point[r], A[i])


answer = 0
candidates = []
for p_list in root_point:
    answer += heapq.heappop(root_point[p_list])
    candidates.extend(root_point[p_list])

remain = 2 * (N-M-1) - len(set(V))
candidates.sort()
answer += sum(candidates[:remain])
print(answer)

Solution (Python):
import sys
from collections import deque, defaultdict
import heapq

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()


def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    
    A[by] = bx

edges = [[] for _ in range(N)]
V = [i for i in range(N)]
for _ in range(M):
    x, y = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)
    edges[x].append(y)
    edges[y].append(x)

for i in range(N):
    V[i] = find(V, i)

if M == N - 1:
    print(0); exit()
elif N < 2 * (N-M-1):
    print('Impossible'); exit()

root_point = defaultdict(list)
for i in range(N):
    r = V[i]
    heapq.heappush(root_point[r], A[i])


answer = 0
candidates = []
for p_list in root_point:
    answer += heapq.heappop(root_point[p_list])
    candidates.extend(root_point[p_list])

remain = 2 * (N-M-1) - len(set(V))
candidates.sort()
answer += sum(candidates[:remain])
print(answer)

Solution (Python):
import heapq
from collections import defaultdict
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  
        self.rank = [0] * (n + 1)

    def find(self, x):  
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N, M = map(int, input().split())

    A = list(map(int, input().split()))

    uf = UF_tree(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.unite(x, y)

    d = defaultdict(list)
    for i in range(N):
        heapq.heappush(d[uf.find(i)], A[i])

    if M == N - 1:
        print(0)
        exit()
    elif N < 2 * (N - M - 1):
        print("Impossible")
        exit()

    nodes = 2 * (N - M - 1)
    ans = 0
    tmp = []
    for k, v in d.items():
        ans += heapq.heappop(v)
        tmp.extend(v)
        nodes -= 1

    tmp.sort()
    ans += sum(tmp[:nodes])
    print(ans)

Solution (Python):
import sys
from heapq import heapify, heappop, heappush

class UFT(): 
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1
def solve():
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    parent = UFT(N)
    for i in range(M):
        x, y = map(int, input().split())
        parent.unite(x, y)
    totalForest = 0
    minCost = 0
    minF = dict()
    for i in range(N):
        a = parent.find(i)
        if a in minF: heappush(minF[a], A[i])
        else: 
            minF[a] = []
            heapify(minF[a])
            heappush(minF[a], A[i])
            totalForest += 1

    f = []
    heapify(f)
    sonNode = []
    heapify(sonNode) 
    if totalForest > 1:
        for key in minF: 
            minCost += heappop(minF[key])
            while minF[key]: heappush(sonNode, heappop(minF[key]))
   
    for _ in range(max(totalForest - 2, 0)):
        if not sonNode: 
            print("Impossible")
            break
        minCost += heappop(sonNode)
    else: print(minCost)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
 
class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N, M = map(int, input().split())
a = list(map(int, input().split()))
uf = Unionfind(N)

for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x, y)

d = defaultdict(list)

for i in range(N):
    d[uf.root(i)].append(a[i])

keys = list(d.keys())

if len(keys)==1:
    print(0)
    exit()

if N<2*(len(keys)-1):
    print('Impossible')
    exit()
    
for k in keys:
    d[k].sort()

ans = 0
l = []

for k in keys:
    ans += d[k][0]
    l += d[k][1:]

l.sort()
ans += sum(l[:len(keys)-2])

print(ans)

Solution (Python):
N,M = map(int,input().split())
A = list(map(int,input().split()))
XY = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y in XY:
    if uf.is_same(x,y): continue
    uf.unite(x,y)
for i in range(N):
    uf.root(i)

c = N - uf.count
if c==1:
    print(0)
    exit()
ex = c-2
if c+ex > N:
    print('Impossible')
    exit()

from collections import defaultdict
d = defaultdict(lambda: [])
for i,a in enumerate(A):
    r = uf.root(i)
    d[r].append(a)

ans = 0
hq = []
for k in d.keys():
    s = sorted(d[k])
    ans += s[0]
    for v in s[1:]:
        hq.append(v)

import heapq
heapq.heapify(hq)
for _ in range(ex):
    v = heapq.heappop(hq)
    ans += v
print(ans)

Solution (Python):
import collections
import heapq
N, M = map(int, input().split())
a = list(map(int, input().split()))


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        self.count[x] = self.count[self.root(x)]
        return(self.count[x])


G = unionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    G.unite(x+1, y+1)
A = [(a[i], i) for i in range(N)]


A.sort(key=lambda x: (-G.getCount(x[1]), G.parent[x[1]], x[0]))
a1 = 0
x = 0
ans = 0
t = []
for a, x in A:
    x = G.root(x)
    if len(t) > 0:
        if G.root(t[0][1]) == x:
            heapq.heappush(t, (a, x))
        else:
            a1, y = heapq.heappop(t)
            y = G.root(y)
            ans += (a + a1)
            G.unite(x+1, y+1)
    else:
        heapq.heappush(t, (a, x))

s = set()
for i in range(N):
    s.add(G.root(i))
if len(s) == 1:
    print(ans)
else:
    print("Impossible")

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  

    def get_root(self, x):
        
        if self.nodes[x] < 0:
            return x
        
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        
        
        
        if root_x != root_y:
            
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M=MI()
    A=LI()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    for _ in range(M):
        x,y = MI()
        unite(x,y)
    
    need = N-1-M 
    need *= 2 
    if need > N:
        print("Impossible")
        return 
    if need == 0:
        print(0)
        return

    root = defaultdict(list)
    for i,a in enumerate(A):
        root[get_root(i)].append(a)

    ans = 0
    whole = []
    for list_ in root.values():
        list_.sort()
        ans += list_[0]
        whole.extend(list_[1:])
        need-=1
    whole.sort()
    ans += sum(whole[:need])
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
res = 0
if M == 0:
  if N == 1:
    print(0)
  elif N == 2:
    print(sum(a))
  else: print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N - 1)
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
hs = [[] for _ in range(N + 1)]
for x in range(N):
  y = uf.Find_Root(x)
  heapq.heappush(hs[y], a[x])

c = 0
t = []
for x in range(N):
  if len(hs[x]):
    c += 1
    res += heapq.heappop(hs[x])
    t += hs[x]
t.sort()

if c == 1:
  print(0)
  exit(0)
if len(t) < c - 2:
  print("Impossible")
  exit(0)
for i in range(c - 2):
  if i >= c - 2:
    print("Impossible")
    exit(0)
  res += t[i]
print(res)

Solution (Python):
N,M = map(int,input().split())
A = list(map(int,input().split()))
XY = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
uf = UnionFind(N)

for x,y in XY:
    if uf.is_same(x,y): continue
    uf.unite(x,y)

re = N - uf.count
if re==1:
    print(0)
    exit()
v = (re-1)*2
if v > N:
    print('Impossible')
    exit()

for i in range(N):
    uf.root(i)
ans = 0
used = [0]*N
d = {}
for i in range(N):
    r = uf.root(i)
    if r in d:
        if d[r][0] > A[i]:
            d[r] = (A[i], i)
    else:
        d[r] = (A[i], i)

for a,b in d.values():
    ans += a
    used[b] = 1
rem = v-re
notused = []
for i in range(N):
    if used[i]: continue
    notused.append(A[i])
notused.sort()
ans += sum(notused[:rem])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N, M = map(int, input().split())
a = list(map(int, input().split()))
uf = Unionfind(N)

for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x, y)

d = defaultdict(list)
rs = set()

for i in range(N):
    r = uf.root(i)
    rs.add(r)
    d[r].append(a[i])

if len(rs)==1:
    print(0)
    exit()

if 2*(len(rs)-1)>N:
    print('Impossible')
    exit()
    
ans = 0

for k in d.keys():
    d[k].sort()
    ans += d[k][0]

l = []

for v in d.values():
    l += v[1:]

l.sort()
ans += sum(l[:len(rs)-2])

print(ans)

Solution (Python):
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N)]

for x,y in XY:
    data[x].append(y)
    data[y].append(x)
visitedlst=[]

ittenai=set([i for i in range(0,N)])
while ittenai:
    q=ittenai.pop()
    stack=[q]
    visited=set()
    visited.add(q)
    while stack:
        q=stack.pop()
        for p in data[q]:
            if p not in visited:
                visited.add(p)
                ittenai.remove(p)
                stack.append(p)
    visitedlst.append(visited)
lst=[]
value=0
count=0
for visited in visitedlst:
    visited=sorted([A[i] for i in list(visited)])
    for i in visited[1:]:
        lst.append(i)
    value+=visited[0]
    count+=1
if count==1:
    print(0)

elif len(lst)<(count//2-1)*2+count%2:
    print("Impossible")
else:
    lst.sort()
    value+=sum(lst[:(count//2-1)*2+count%2])
    print(value)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
cost = list(map(int,input().split()))
ab = [list(map(int, input().split(' '))) for i in range(m)]
graph = [[] for i in range(n)]
visited = [0 for i in range(n)]
vers = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
for i in range(n):
  if visited[i] == 0:
    vers.append([])
    stack = [i]
    while stack:
      x = stack.pop()
      visited[x] = 1
      vers[-1].append((cost[x],x))
      for y in graph[x]:
        if visited[y] == 0:
          stack.append(y)
n_grph = len(vers)
if (n_grph-1)*2 > n:
  print("Impossible")
  exit()
for ver in vers:
  ver.sort()
visited = [0 for i in range(n)]
i = [i for i in range(n)]
costi = list(zip(cost,i))
costi.sort()
ans = 0
t = n_grph-2
if t >= 0:
  for ver in vers:
    ans += ver[0][0]
    visited[ver[0][1]] = 1

k = 0
while t > 0:
  c = costi[k][1]
  if visited[c] == 0:
    ans += costi[k][0]
    t -= 1
  k += 1
print(ans)

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            self.n = n
            

        def find(self, x):
            
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            
            return self.find(x) == self.find(y)

        def size(self, x):
            
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            
            return self.parent[x] < 0

        def roots(self):
            
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            
            return len(self.roots())

        def all_group_members(self):
            
            return {r: self.members(r) for r in self.roots()}
    
    N, M = LI()
    a = LI()
    ans = 0
    uf = UnionFind(N)
    for _ in range(M):
        x,y = LI()
        if not uf.same(x,y):
            uf.unite(x,y)
    D = defaultdict(int)
    rep = defaultdict(bool)
    r = uf.roots()
    keep = [-1]*N
    for i in range(N):
        parent = uf.find(i)
        if (not D[parent]) or D[parent] > a[i]:
            D[parent] = a[i]
            keep[parent] = i
    for i in range(N):
        if keep[i]==-1:
            continue
        rep[keep[i]] = True
        ans += D[i]
    loop = uf.group_count()-2
    if loop==-1:
        print(0)
        return
    A = []
    for i,j in enumerate(a):
        A.append([j,i])
    A.sort()
    cur = 0
    for i in range(N):
        if cur>=loop:
            break
        if not rep[A[i][1]]:
            cur +=1
            ans += A[i][0]
    if cur<loop:
        print("Impossible")
        return
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
if N == 1:
  print(0)
  exit(0)
if M == 0 and (N > 2):
  print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
d = [[] for _ in range(N)]
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
for i in range(N):
  d[uf.Find_Root(i)].append(a[i])
res = 0
x = []
y = 0
for i in range(N):
  d[i].sort(reverse = True)
  if len(d[i]):
    res += d[i].pop()
    y += 1
  x += d[i]
if y == 1:
  print(0)
  exit(0)
x.sort()
for i in range((y - 1) * 2 - y):
  if i >= len(x):
    print("Impossible")
    exit(0)
  res += x[i]
print(res)

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*n
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]

def main():
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  uf = UnionFind(n)
  for _ in range(m):
    x,y = map(int, input().split())
    uf.unite(x,y)
  d = dict()
  res = list()
  for i in range(n):
    v = uf.find(i)
    if v not in d:
      d[v] = a[i]
    elif d[v] > a[i]:
      res.append(d[v])
      d[v] = a[i]
    else:
      res.append(a[i])
  t = len(d)
  e = (t-1)*2
  if t == 1:
    return 0
  elif len(res) < e-t:
    return 'Impossible'
  else:
    res.sort()
    return sum(x for x in d.values()) + sum(res[:e-t])
  
print(main())