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):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

    first_mins = []
    other_vals = []
    
    all_members = uf.get_all_members()
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        vs = []
        for m in members:
            vs.append(al[m])
        vs.sort()
        first_mins.append(vs[0])
        for i,v in enumerate(vs):
            if i > 0:
                other_vals.append(v)

    
    ans = 0
    ans += sum(first_mins)
    rem = len(all_members)-2
    if len(other_vals) < rem:
        print('Impossible')
        exit()
    other_vals.sort()
    ans += sum(other_vals[:rem])
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

    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), a, *q = [[*map(int,o.split())] for o in open(0)]
UF = UnionFind(n)
k = (n - m - 1) * 2
if k > n:
    exit(print("Impossible"))
if not k:
    exit(print(0))

for c, f in q:
    UF.union(c, f)

from collections import*
d = defaultdict(list)
for e, i in enumerate(a):
    d[UF.find(e)] += i,

ans, b = 0, []
for r, p in d.items():
    p.sort()
    ans += p.pop(0)
    b += p
    k -= 1
b.sort()
print(ans + sum(b[:k]))

Solution (Python):
from heapq import heappop, heappush
from collections import defaultdict

class MeldableHeap():
    def __init__(self):
        self.size = 0
        self.heap = list()
        self.added = 0

    def top(self):
        if not self.heap:
            return None
        return self.heap[0] + self.added

    def pop(self):
        if not self.heap:
            return None
        res = heappop(self.heap)
        self.size -= 1
        return res + self.added

    def push(self, x):
        heappush(self.heap, x - self.added)
        self.size += 1

    def add(self, x):
        self.added += x

    def meld(self, other): 
        res = MeldableHeap()
        if self.size < other.size:
            self, other = other, self
        res.heap = self.heap
        res.size = self.size
        for _ in range(other.size):
            res.push(other.pop() - self.added)
        return res

N, M = map(int, input().split())
A = list(map(int, input().split()))
edge = [tuple(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for x, y in edge:
    graph[x].append(y)
    graph[y].append(x)

used = [0 for _ in range(N)]
heap = defaultdict(MeldableHeap)
roots = []

for root in range(N):
    if used[root]:
        continue
    roots.append(root)
    heap[root].push(A[root])
    used[root] = 1
    stack = [root]
    while stack:
        node = stack.pop()
        for adj in graph[node]:
            if used[adj]:
                continue
            used[adj] = 1
            heap[root].push(A[adj])
            stack.append(adj)

single = set()

for k, v in heap.items():
    if v.size == 1:
        single.add(k)

roots.sort(key=lambda x: x in single)

res = 0
tmp = heap[roots[0]]

for i in range(1, len(roots)):
    if tmp.size == 0:
        print('Impossible')
        break
    v = heap[roots[i]]
    a = tmp.pop()
    b = v.pop()
    tmp = tmp.meld(v)
    res += a + b
else:
    print(res)

Solution (Python):
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  
  
  
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)

ren=n-m-len(dg1c)
topheap=[]
ans=0
ary=[]
cnt=0




for k in dg.keys():
  t=min(dg[k])
  ans+=t
  cnt+=1
  dg[k].remove(t)
  ary+=dg[k]
ary.sort()
ans+=sum(ary[:(n-m-1)*2-cnt])
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


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

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

    
    def unite(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[x] += self.par[y]
            self.par[y] = x

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

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

n,m = readints()

a = readints()

u = UnionFind(n)
for i in range(m):
    x,y = readints()
    u.unite(x,y)

for i in range(n):
    u.find(i)

b = {}
for i in range(n):
    if u.par[i]<0:
        b[i] = (a[i],i)

for i,p in enumerate(u.par):    
    if p>=0 and b[p][0]>a[i]:
        b[p] = (a[i],i)

for v in b.values():
    a[v[1]]=10**10

a.sort()
if len(b)==1:
    print(0)
elif n < len(b)*2-2:
    print('Impossible')
else:
    print(sum([x[0] for x in b.values()]) + sum(a[:len(b)-2]))

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class UnionFind:
    """ Union-Find木 """

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

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

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

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

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

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M = MAP()
A = LIST()
uf = UnionFind(N)
for i in range(M):
    a, b = MAP()
    uf.union(a, b)

L = uf.get_size()
K = (L-1) * 2 
if K > N:
    print('Impossible')
    exit()
elif K == 0:
    print(0)
    exit()

adjli = [[] for i in range(N)]
for i in range(N):
    root = uf.find(i)
    adjli[root].append(A[i])

ans = 0
B = []
for i in range(N):
    if adjli[i]:
        adjli[i].sort(reverse=1)
        ans += adjli[i].pop()
        B += adjli[i]
        K -= 1

B.sort()
ans += sum(B[:K])
print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class UnionFind:
    """ Union-Find木 """

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

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

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

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

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

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M = MAP()
A = LIST()
uf = UnionFind(N)
for i in range(M):
    a, b = MAP()
    uf.union(a, b)

L = uf.get_size()
K = (L-1) * 2 
if K > N:
    print('Impossible')
    exit()
elif K == 0:
    print(0)
    exit()

adjli = [[] for i in range(N)]
for i in range(N):
    root = uf.find(i)
    adjli[root].append(A[i])

ans = 0
B = []
for i in range(N):
    if adjli[i]:
        adjli[i].sort(reverse=1)
        ans += adjli[i].pop()
        B += adjli[i]
        K -= 1

B.sort()
ans += sum(B[:K])
print(ans)

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

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

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

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
          x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

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

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

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) 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 num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
from bisect import *
from collections import defaultdict
def solve():
  ans = 0
  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.union(x,y)
  if N>2*(M+1):
    return 'Impossible'
  if N-M==1:
    return 0
  d = defaultdict(lambda: [])
  for i in range(N):
    r = uf.find(i)
    if r<0:
      d[i].append(A[i])
    else:
      d[r].append(A[i])
  lis1 = []
  for v in d.values():
    mini = min(v)
    ans += mini
    v.remove(mini)
    for l in v:
      insort_right(lis1,l)
  ans += sum(lis1[:(N-M-2)])
  return ans
print(solve())

Solution (Python):
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1
        
N, M = map(int, input().split())
A = list(map(int, input().split()))
uf = UF(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x,y)

D = {}
for x, a in enumerate(A):
    c = uf.find(x)
    if c not in D: D[c]=[]
    D[c].append(a)

ans = 0
L = []
for d in D.values():
    d.sort()
    ans += d[0]
    L += d[1:]

L.sort()

P = len(D)-2
if len(D)==1:
    ans = 0
elif len(L)>=P:
    ans += sum(L[:len(D)-2])
else:
    ans = 'Impossible'

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import heapq

n, m = map(int, input().split())
if m == n-1:
  print(0)
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
G = [[] for _ in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  G[x].append(y)
  G[y].append(x)
ans = 0
L = []
seen = [False]*n
def dfs(v):
  global ans
  K = []
  stack = [v]
  while stack:
    v = stack.pop()
    heapq.heappush(K, A[v])
    seen[v] = True
    for nv in G[v]:
      if seen[nv]:
        continue
      stack.append(nv)
  ans += heapq.heappop(K)
  for k in K:
    heapq.heappush(L, k)
for i in range(n):
  if not seen[i]:
    dfs(i)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import heapq

n, m = map(int, input().split())
if m == n-1:
  print(0)
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
G = [[] for _ in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  G[x].append(y)
  G[y].append(x)
ans = 0
L = []
seen = [False]*n
def dfs(v):
  global ans
  K = []
  stack = [v]
  while stack:
    v = stack.pop()
    heapq.heappush(K, A[v])
    seen[v] = True
    for nv in G[v]:
      if seen[nv]:
        continue
      stack.append(nv)
  ans += heapq.heappop(K)
  for k in K:
    heapq.heappush(L, k)
for i in range(n):
  if not seen[i]:
    dfs(i)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

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

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

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

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        
        others.extend(hqs[i])

others.sort()
rem = p - len(ans)

ans.extend(others[:rem])

print(sum(ans))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

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

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

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

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        others += hqs[i]

others.sort()
rem = p - len(ans)
ans += others[:rem]

print(sum(ans))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

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

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

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

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

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        for j in hqs[i]:
            others.append(j)

others.sort()
rem = p - len(ans)
ans = ans + others[:rem]

print(sum(ans))

Solution (Python):
n,m=map(int,input().split())

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

union=[-1]*n

tree=[[] for _ in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    tree[x].append(y)
    tree[y].append(x)

cnt=-1
for i in range(n):
    if union[i]==-1:
        stack=[i]
        cnt+=1
        while len(stack)>0:
            tmp=stack.pop()
            union[tmp]=cnt
            for item in tree[tmp]:
                if union[item]==-1:
                    union[item]=cnt
                    stack.append(item)

if cnt==0:
    print(0)
    exit()

cost=[[] for _ in range(cnt+1)]

for i,aa in enumerate(a):
    cost[union[i]].append(aa)

import heapq

del_list=[]
kouho_list=[]

ans=0


for i in range(cnt+1):
    tmp=min(cost[i])
    ans+=tmp
    del_list.append(tmp)
    kouho_list+=cost[i]
    


heapq.heapify(kouho_list)
heapq.heapify(del_list)

for _ in range(2*(n-m-1)-(cnt+1)):
    
    while 1:
        
        if len(kouho_list)>0:
            tmp=heapq.heappop(kouho_list)
        else:
            print("Impossible")
            exit()
        
        if len(del_list)>0:
            if del_list[0]!=tmp:
                break
            else:
                heapq.heappop(del_list)
        else:
            break
        
    ans+=tmp

print(ans)

Solution (Python):
class UnionFind():
    '''
    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 is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush, heapify

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x, y)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    if N - 1 == M:
        print(0)
        return
    node = [0] * N
    qtable = [[] for _ in range(N)]
    allq = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(qtable[node[i]], A[i])
    ans = 0
    cnt = 0
    for i in range(N):
        if qtable[i]:
            ans += heappop(qtable[i])
            cnt += 1
        allq.extend(qtable[i])

    heapify(allq)
    for i in range(select_node-cnt):
        ans += heappop(allq)
    print(ans)

main()

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


from bisect import bisect_left, bisect_right
import heapq




input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)

    
    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 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 same_check(self, x, y):
        return self.find(x) == self.find(y)

def main():
    n, m = getList()
    uf = UnionFind(n)
    costs = getList()

    q = []
    for i, c in enumerate(costs):
        heapq.heappush(q, (c, i))
    
    hen = 0
    for _ in range(m):
        a, b = getList()
        if not uf.same_check(a, b):
            uf.union(a,b)
            hen += 1
 
    
    ans = 0
    used = defaultdict(int)
    kaburi = []
    mc = 0
    while(q):
        c1, m1 = heapq.heappop(q)
        if uf.find(m1) not in used.keys():
            ans += c1
            used[uf.find(m1)] = 1
            mc += 1
        else:
            heapq.heappush(kaburi, (c1, m1))

    
    if mc == 1:
        print(0)
        return 

    if len(kaburi) >= 2 * (n - hen - 1) - mc:
        for _ in range(2 * (n - hen - 1) - mc):
            c1, m1 = heapq.heappop(kaburi)
            ans += c1
        print(ans)
        return 
    else:
        print("Impossible")
        return


if __name__ == "__main__":
    main()