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):
from collections import defaultdict
import heapq

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    UF.union(x, y)

UF.all_find()


D = defaultdict(list)
for i in range(N):
    D[UF.par[i]].append(A[i])


group = len(D)
if group == 1:
    print(0)
    exit()


for key in D.keys():
    heapq.heapify(D[key])


ans = 0
for key in D.keys():
    ans += heapq.heappop(D[key])


remain = []
for value in D.values():
    remain.extend(value)

remain.sort()
if len(remain) < group - 2:
    print("Impossible")
else:
    ans += sum(remain[:group - 2])
    print(ans)

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
A = [int(x) for x in input().split()]


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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


if 2 * (N - M - 1) > N:
    print('Impossible')
elif N - M == 1:
    print(0)
else:
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.union(x, y)

    tree = defaultdict(list)
    for i in range(N):
        tree[uf.find(i)].append(A[i])

    ans = 0
    rest = []
    for v in tree.values():
        x = min(v)
        v.remove(x)
        rest += v
        ans += x

    rest = sorted(rest)
    ans += sum(rest[:N - M - 2])
    print(ans)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()
  if M == N-1:
    print(0); exit()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in mins.items():
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:g-2])
  print(ans)

class union_find:
  def __init__(self, n): self.par = [-1] * n; self.rank = [0] * n
  def __repr__(self): return "union_find({0})".format([self.root(i) for i in range(n)])
  def unite(self, x, y):
    x = self.root(x); y = self.root(y)
    if x == y: return
    if self.rank[x] < self.rank[y]: self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]: self.rank[x] += 1
  def root(self, x):
    if self.par[x] == -1: return x
    else: self.par[x] = self.root(self.par[x]); return self.par[x]
  def same(self, x, y): return self.root(x) == self.root(y)

main()

Solution (Python):
import sys
from collections import defaultdict

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

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

  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1<root2:
      self.table[root1]+=self.table[root2]
      self.table[root2]=root1
    else:
      self.table[root2]+=self.table[root1]
      self.table[root1]=root2

N,M=map(int,input().split())
A=[int(i) for i in input().split()]
uf=UnionFind(N)
for i in range(M):
  x,y=map(int,input().split())
  uf.union(x,y)
groups=defaultdict(list)
for j in range(N):
  groups[uf.find(j)].append(A[j])

groups = [sorted(g, reverse=True) for g in groups.values()]

if len(groups) == 1:
  print(0)
  sys.exit()

ans=0
cnt=[]
for group in groups:
  ans+=group.pop()
  cnt+=group

if len(groups)-2 > len(cnt):
  print("Impossible")
else:
  cnt.sort()
  ans+=sum(cnt[:len(groups)-2])
  print(ans)

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

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

par=[i for i in range(N)]

def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		par[x]=r
		return r

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y


for i in range(M):
	x,y=map(int,raw_input().split())
	unite(x,y)


group_cost=defaultdict(lambda: [])

for i in range(N):
	root(i)
	group_cost[par[i]].append(cost[i])


H = []

ans=0
for v in group_cost.values():
	v=sorted(v)
	ans+=v[0]
	H.append(v[1:])

nokori_cost=list(heapq.merge(*H))


if N < 2*(N-M-1):
	print "Impossible"
elif M == N-1:
	print 0
else:
	ans += sum(nokori_cost[:2*(N-M-1) - len(group_cost.keys())])
	print ans

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

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

if M==N-1:
	print 0
	quit()

nl=[ [] for i in range(N) ]

for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

group_cost=defaultdict(lambda: [])

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	heapq.heappush(group_cost[start],cost[start])
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)
				heapq.heappush(group_cost[start],cost[i])

for i in range(N):
	if V[i] is None:
		dfs(i)


H = []

ans=0
for v in group_cost.values():
	v=sorted(v)
	ans+=v[0]
	H.append(v[1:])

nokori_cost=list(heapq.merge(*H))


if N < 2*(N-M-1):
	print "Impossible"
elif M == N-1:
	print 0
else:
	ans += sum(nokori_cost[:2*(N-M-1) - len(group_cost.keys())])
	print ans

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

N, M = map(int, input().split())
costs = list(map(int, input().split()))
treemin = [(cost, i) for i, cost in enumerate(costs)] 

parent = list(range(N))
rank = [0] * (N)
def getRoot(x):
  if parent[x] == x:
    return x
  else:
    
    parent[x] = getRoot(parent[x])
    return parent[x]

def unite(x, y):
  global treemin
  xRoot = getRoot(x)
  yRoot = getRoot(y)
  if xRoot == yRoot:
    return
  if rank[xRoot] < rank[yRoot]:
    parent[xRoot] = yRoot
    if treemin[yRoot][0] > treemin[xRoot][0]:
      treemin[yRoot] = treemin[xRoot]
  else:
    parent[yRoot] = xRoot
    if treemin[xRoot][0] > treemin[yRoot][0]:
      treemin[xRoot] = treemin[yRoot]
    if rank[xRoot] == rank[yRoot]:
      rank[xRoot] += 1

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

ans = 0
numtree = 0
exclude = set()
for i in range(N):
  if parent[i] == i:
    numtree += 1
    ans += treemin[i][0]
    exclude.add(treemin[i][1])

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

heap = []
for i in range(N):
  if i not in exclude:
    heappush(heap, costs[i])

ans += sum(nsmallest(numtree - 2, heap))
print(ans)

Solution (Python):

from collections import defaultdict
from heapq import merge
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] 
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: 
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
res = 0 

for k, v in D.items():
    v = sorted(v)
    res += v[0]
    H.append(v[1:])
 
if N < 2*(N-M-1):
    print("Impossible")
elif M == N-1:
    print(0)
else:
    res += sum(list(merge(*H))[:2*(N-M-1) - len(D.keys())])
    print(res)

Solution (Python):

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] 
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: 
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
res = 0 

for k, v in D.items():
    v = sorted(v)
    res += v[0]
    H.extend(v[1:])
 
if N < 2*(N-M-1):
    print("Impossible")
elif M == N-1:
    print(0)
else:
    res += sum(sorted(H)[:2*(N-M-1) - len(D.keys())])
    print(res)

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


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, readline().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        mins[uf.find(i)].append(a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    others = []
    for v in mins.values():
        v.sort(reverse=True)
        ans += v.pop()
        others += v
    others.sort()
    return 'Impossible' if len(others) < len(mins) - 2 else ans + sum(others[:len(mins) - 2])

print(main())

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


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, readline().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        mins[uf.find(i)].append(a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    others = []
    for v in mins.values():
        v.sort(reverse=True)
        ans += v.pop()
        others += v
    others.sort()
    return 'Impossible' if len(others) < len(mins) - 2 else ans + sum(others[:len(mins) - 2])

print(main())

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

if M == N-1:
    print(0)
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)

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

if M == N-1:
    print(0)
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    root(i)
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m = LI()
    a = LI()
    uf = UnionFind(n)
    for _ in range(m):
        x,y = LI()
        uf.union(x,y)

    d = collections.defaultdict(list)
    for i in range(n):
        d[uf.find(i)].append(a[i])

    l = len(d)
    if l == 1:
        return 0
    r = 0
    b = []
    for v in d.values():
        v.sort()
        r += v[0]
        b += v[1:]
    b.sort()
    if l % 2 == 0:
        ll = (l // 2 - 1) * 2
    else:
        ll = (l // 2 - 1) * 2 + 1
    if len(b) < ll:
        return 'Impossible'
    r += sum(b[:ll])
    return r



print(main())

Solution (Python):
from collections import deque, defaultdict
from heapq import heapify, heappop, merge, heapreplace


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

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

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = defaultdict(list)
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    if len(roots) == 1:
        return 0
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    ans = 0
    queue = []
    for l in roots.values():
        l.sort()
        ans += l[0]
        queue.append(l[1:])
    lm = n - m - 2
    if lm > 0:
        mm = merge(*queue)
        for _ in range(lm):
            ans += next(mm)
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))

Solution (Python):
from heapq import heapify, heappop

N, M = map(int, input().split())
As = [(A, i) for i, A in enumerate(map(int, input().split()))]

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


def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y: return
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


parent = [i for i in range(N)]
rank = [0] * N

for i in range(M):
    x, y = map(int, input().split())
    union(x, y)

for i in range(N):
    find(i)


minAs = {}
for A, i in As:
    p = parent[i]
    minAs[p] = min(minAs.get(p, (float('inf'), 0)), (A, i))

done = [False] * N
ans = 0
for (A, i) in minAs.values():
    done[i] = True
    ans += A


heapify(As)
rest = N - M - 2
while rest > 0:
    A, i = heappop(As)
    if not done[i]:
        ans += A
        rest -= 1

print(ans)

Solution (Python):
from collections import defaultdict

class UnionFind(object):

    def __init__(self, n):
        self.table = [-1] * N

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

    def union(self, x1, x2):
        root1 = self.find(x1)
        root2 = self.find(x2)
        if root1 < root2:
            self.table[root1] += self.table[root2]
            self.table[root2] = root1
        else:
            self.table[root2] += self.table[root1]
            self.table[root1] = root2

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
xy = [[int(x) for x in input().split()] for i in range(M)]

def solve(N, M, A, xy):

    uf = UnionFind(N)
    for x, y in xy:
        uf.union(x, y)

    groups = defaultdict(list)
    for i in range(N):
        groups[uf.find(i)].append(A[i])

    groups = [sorted(g, reverse=True) for g in groups.values()]

    if len(groups) == 1:
        return 0

    r = 0

    xs = []
    for group in groups:
        r += group.pop()
        xs += group

    if len(groups) == 2:
        return r

    if len(groups) - 2 > len(xs):
        return "Impossible"

    xs.sort()
    r += sum(xs[:len(groups) - 2])

    return r

print(solve(N, M, A, xy))

Solution (Python):

import numpy as np

N, M = map(int, input().split())
a_list = list(map(int, input().split()))

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    conn_ = [st]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                conn_.append(t)
                
    args = np.argsort(conn)
    res += conn[args[0]]
    a_list[conn_[args[0]]] = 2000000000

a_list.sort()

if connec == 1:
    print(0)
elif len(a_list) < 2*connec - 2:
    print('Impossible')
else:
    print(res + sum(a_list[:(connec - 2)]))

Solution (Python):
def dfs(i):
    global ns,flags,a
    if flags[i]:
        return []
    flags[i]=True
    out=[a[i]]
    for n in ns[i]:
        out.extend(dfs(n))
    return out
        

line=input().split()
N=int(line[0])
M=int(line[1])
a=input().split()
ns={}
for i in range(N):
    a[i]=int(a[i])
    ns[i]=[]


for i in range(M):
    line=input().split()
    x=int(line[0])
    y=int(line[1])
    ns[x].append(y)
    ns[y].append(x)

flags=[False for i in range(N)]
sets=[]
for i in range(N):
    if not flags[i]:
        sets.append(dfs(i))

if len(sets)==1:
    print ("0")
    exit(0)
if (len(sets)-1)*2>N:
    print ("Impossible")
    exit(0)

        
tot=0
for s in sets:
    s.sort()
    tot+=s[0]
more=(len(sets)-1)*2-len(sets)
al=[]
for s in sets:
    for p in s[1:]:
        al.append(p)
al.sort()
for i in range(more):
    tot+=al[i]
print(tot)

Solution (Python):
N, M = map(int, input().split())
*A, = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

from collections import deque
used = set()
ans = 0
cnt = 0
R = []
for i in range(N):
    if i in used:
        continue
    tmp = [A[i]]
    deq = deque([i])
    used.add(i)
    while deq:
        v = deq.popleft()
        for w in G[v]:
            if w in used:
                continue
            tmp.append(A[w])
            deq.append(w)
            used.add(w)
    tmp.sort()
    ans += tmp[0]
    R += tmp[1:]
    cnt += 1
if len(R) + 2 < cnt:
    print("Impossible")
    exit(0)
if cnt == 1:
    print(0)
    exit(0)
R.sort()
ans += sum(R[:cnt-2])
print(ans)