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 heapq
import itertools


class UnionFind:

    def __init__(self, size: int):
        
        
        self.size = size
        self.parent = [-1] * size

    def find(self, x: int) -> int:
        """
        xを含む集合の代表を求める
        """
        if self.parent[x] < 0:
            return x
        
        same_group_items = []
        while self.parent[x] >= 0:
            same_group_items.append(x)
            x = self.parent[x]
        for child in same_group_items:
            self.parent[child] = x
        return x

    def unite(self, x: int, y: int):
        """
        xを含む集合とyを含む集合を併合する
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.parent[root_x] >= self.parent[root_y]:
                self.parent[root_x] += self.parent[root_y]
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] += self.parent[root_x]
                self.parent[root_x] = root_y

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def count_group(self) -> int:
        """
        集合の数を数える。
        """
        count = 0
        for i in range(self.size):
            if self.parent[i] < 0:
                count += 1
        return count


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

if n-1 == m:
    print(0)
    exit()
if n < 2*(n-m-1):
    print('Impossible')
    exit()


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

hs = [[] for i in range(n)]
for i in range(n):
    p = uf.find(i)
    heapq.heappush(hs[p], a[i])
cost = 0
for i in range(n):
    if len(hs[i]) > 0:
        cost += heapq.heappop(hs[i])
hs = list(itertools.chain.from_iterable(hs))
heapq.heapify(hs)
for i in range(uf.count_group(), 2*(n-m-1)):
    cost += heapq.heappop(hs)
print(cost)

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)]

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * 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._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

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)

from collections import defaultdict
dic = defaultdict(lambda: set())
for i in range(N):
    dic[uf.root(i)].add(i)

need = (len(dic)-1)*2
if need > N:
    print('Impossible')
    exit()

ans = used = 0
import heapq
hq = []
heapq.heapify(hq)
for r,vs in dic.items():
    mini = -1
    mina = 10**9+1
    for i in vs:
        if A[i] < mina:
            mina = A[i]
            mini = i
    ans += mina
    used += 1
    for i in vs:
        if i==mini: continue
        heapq.heappush(hq, A[i])

for _ in range(need - used):
    ans += heapq.heappop(hq)
print(ans)

Solution (Python):
n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*(n-m-1) > n:
    print("Impossible")
    exit()

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

u = Unionfind(n)
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    u.union(x,y)
count = 2*(n-m-1)
l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        l[i].append(a[i])
    else:
        l[x].append(a[i])

ans = 0
h = []
for i in range(n):
    if l[i]:
        l[i].sort()
        ans += l[i][0]
        count -= 1
        for j in l[i][1:]:
            h.append(j)
h.sort()
ans += sum(h[:count])
print(ans)

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

n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*(n-m-1) > n:
    print("Impossible")
    exit()

e = [[] for i in range(n)]
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    e[x].append(y)
    e[y].append(x)

def dfs(x):
    l = []
    d[x] = 1
    l.append(a[x])
    q = deque([])
    q.append(x)
    while q:
        now = q.pop()
        for nex in e[now]:
            if d[nex] > 0:
                continue
            l.append(a[nex])
            d[nex] = 1
            q.append(nex)
    l.sort()
    ans = l[0]
    
    for i in l[1:]:
        h.append(i)
    return ans
count = 2*(n-m-1)
d = [-1]*n
ans = 0
h = []
for i in range(n):
    if d[i] < 0:
        ans += dfs(i)
        count -= 1
if count > 0:
    h.sort()
    ans += sum(h[:count])
print(ans)

Solution (Python):
import sys
import heapq

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()


N, M = inm()
A = inl()
assert len(A) == N


def solve():
    uf = UnionFind(N)
    for _ in range(M):
        x, y = inm()
        uf.union(x, y, pay=False)
    rs = uf.roots()
    rs.sort(key=lambda x: uf.size(x), reverse=True)
    s = rs[0]
    for i in range(1, len(rs)):
        if not uf.union(s, rs[i], pay=True):
            return "Impossible"
    return uf.paid_cost()


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n
        self._cost_table = [[A[i]] for i in range(n)]  
        self._paid_cost = 0

    def paid_cost(self):
        return self._paid_cost

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y, pay):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

        if pay:
            if not self._cost_table[x]:
                return False
            ax = heapq.heappop(self._cost_table[x])
            if not self._cost_table[y]:
                return False
            ay = heapq.heappop(self._cost_table[y])
            self._paid_cost += ax + ay

        for z in self._cost_table[y]:
            heapq.heappush(self._cost_table[x], z)
        self._cost_table[y] = []
        return True

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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

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

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


print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


from functools import lru_cache


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]


class UnionFind:
    def __init__(self, elements=None):
        """Create a new empty union-find structure.
        If *elements* is an iterable, this structure will be initialized
        with the discrete partition on the given set of elements.
        """
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, i):
        """Find and return the name of the set containing the i."""

        
        if i not in self.parents:
            self.parents[i] = i
            self.weights[i] = 1
            return i

        
        path = [i]
        root = self.parents[i]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        return iter(self.parents)

    def union(self, *objects):
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

    def __len__(self):
        return len(self.parents)


def main():
    mod = 10**9+7
    

    
    N, M = map(int, input().split())
    A = tuple(map(int, input().split())) 
    
    
    tree=UnionFind(list(range(N)))
    for i in range(M):
        x,y=map(int, input().split())
        tree.union(x,y)
    d=dict()
    for i in range(N):
        root=tree[i]
        if root not in d:
            d[root]=[]
        heappush(d[root],A[i])
    nr=len(d.keys())
    if nr==1:
        print(0)
        return

    if 2*(nr-1)>N:
        print('Impossible')
        return 
    
    ans=0
    
    ocount=0
    As=[]
    
    for j, q in d.items():
        a=heappop(q)
        ans+=a
        As+=q
    
    As.sort()
    for i in range(0,nr-2):
        ans+=As[i]
    


    print(ans)

    






if __name__ == "__main__":
    main()

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

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

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

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

    def get_size(self, x):
        return self.size[self.find(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)
group = defaultdict(list)
for i in range(N):
    group[uf.find(i)].append(a[i])
if len(group) == 1:
    print(0)
    exit()
ans = 0
rem = []
for k, v in group.items():
    v.sort()
    ans += v[0]
    rem += v[1:]
if len(rem) < len(group) - 2:
    print('Impossible')
else:
    rem.sort()
    ans += sum(rem[:len(group) - 2])
    print(ans)

Solution (Python):
n, m = map(int,input().split())
if n-m == 1:
    print(0)
    exit()
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    way[x].append(y)
    way[y].append(x)


import queue
def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n)]
    q = queue.Queue()
    for i in range(n):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

grp = grouping(n,way)
if len(grp)-2 > n-len(grp):
    print("Impossible")
    exit()
o2 = [0 for i in range(n-len(grp))]
o1 = [0 for i in range(len(grp))]
i1 = 0

for j,gi in enumerate(grp):
    m = 10**10
    f = True
    for i in gi:
        if m > a[i]:
            if f:
                f = False
            else:
                o2[i1] = m
                i1 += 1
            m = a[i]
        else:
            o2[i1] = a[i]
            i1 += 1
    o1[j] = m

o2.sort()
ans = sum(o1)
for i in range(len(o1)-2):
    ans += o2[i]
print(ans)

Solution (Python):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].add(v)
    ns[v].add(u)

score = 0
count = 0
others = []
seen = [False] * n
for start in range(n):
    if seen[start]:
        continue
    count += 1
    q = [start]
    s = [a[start]]
    seen[start] = True
    while q:
        u = q.pop()
        for v in ns[u]:
            if not seen[v]:
                heapq.heappush(s, a[v])
                q.append(v)
                seen[v] = True
    score += heapq.heappop(s)
    for item in s:
        heapq.heappush(others, item)

if n<2*(count-1):
    print("Impossible")
elif count==1:
    print(0)
else:
    for _ in range(2*(count-1)-count):
        score += heapq.heappop(others)
    else:
        print(score)

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys,heapq

input=sys.stdin.readline

N,M=map(int,input().split())
a=list(map(int,input().split()))
uf=UnionFindVerSize(N)
for i in range(M):
    x,y=map(int,input().split())
    uf.unite(x,y)

dic={}
for i in range(0,N):
    if uf.find_root(i) not in dic:
        dic[uf.find_root(i)]=[]
        heapq.heapify(dic[uf.find_root(i)])
    heapq.heappush(dic[uf.find_root(i)],a[i])

m=len(dic)
if m==1:
    print(0)
    exit()
ans=0
for i in dic:
    ans+=heapq.heappop(dic[i])

data=[]
for i in dic:
    data+=dic[i]
data.sort()
if len(data)<m-2:
    print("Impossible")
else:
    print(ans+sum(data[:m-2]))

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
XY=[list(map(int,input().split())) for i in range(M)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
u=UnionFind(N)
for x,y in XY:
    u.unite(x,y)
if u.size(0)==N:
    print(0);exit()
d={}
x=[]
for i,a in enumerate(A):
    r=u.root(i)
    if r not in d:
        d[r]=a
    elif a<d[r]:
        x.append(d[r])
        d[r]=a
    else:
        x.append(a)
rem=2*(N-1-M)-len(d)
print(sum([v for v in d.values()])+sum(sorted(x)[:rem]) if len(x)>=rem else "Impossible")

Solution (Python):
import sys
from collections import defaultdict
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
dic = defaultdict(list)
used = [False]*N
ans = 0
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
for i in range(N):
  dic[U.find(i)].append((A[i],i))
if len(dic.keys())==1:
  print(0)
  sys.exit()
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0][0]
  used[dic[k][0][1]] = True
B = sorted((c,i) for i,c in enumerate(A))
cnt = len(dic.keys())-2
for i in range(N):
  if cnt==0:
    break
  if used[B[i][1]]:
    continue
  ans += B[i][0]
  cnt -= 1
if cnt > 0:
  print('Impossible')
else:
  print(ans)

Solution (Python):
from heapq import heappush, heappop
from collections import defaultdict
n,m = map(int,input().split())
a = list(map(int,input().split()))

rank = [1] * n
par = [i for i in range(n)]
def root(x):
  if x == par[x]:
    return x
  par[x] = root(par[x])
  return par[x]
def union(a,b):
  a = root(a)
  b = root(b)
  if rank[a] < rank[b]:a,b = b,a
  if a == b: return False
  par[b] = a
  rank[a] += rank[b]
  return True
for _ in range(m):
  x,y = map(int, input().split())
  union(x,y)
d = defaultdict(list)
q = []
for i in range(n):
  ai = a[i]
  heappush(q,(ai,i))
  ri = root(i)
  heappush(d[ri],(ai,i))
if len(d.keys()) == 1:
  print(0)
else:
  ans = 0
  tmp = 0
  c = [0] * n

  for i in d.keys():
    tmp += 1
    t,p = heappop(d[i])
    c[p] = 1
    ans += t
  if 2*tmp-2 > n:
    print("Impossible")
  else:
    for _ in range(tmp-2):
      p,i = heappop(q)
      while c[i]:
        p,i = heappop(q)
      ans += p
    print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


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

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

par = [uf.find(i) for i in range(N)]
d = {}
for i, p in enumerate(par):
  if p in d:
    d[p].append(A[i])
  else:
    d[p] = [A[i]]

num = len(d)
if num == 1:
  print(0)
  quit()

a = []
ans = 0
for p in d:
  d[p].sort(reverse=True)
  ans += d[p].pop()
  a += d[p]

a.sort()
n = 2*(N - M - 1) - num
if len(a) < n:
  print('Impossible')
else:
  print(sum(a[:n]) + ans)

Solution (Python):
from collections import deque
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
F = []
hist = [0 for _ in range(N)]
for i in range(N):
    T = []
    if hist[i]==0:
        que = deque([i])
        hist[i]=1
        heapq.heappush(T,A[i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    hist[y]=1
                    heapq.heappush(T,A[y])
        F.append(T)
K = len(F)
if K>N//2+1:        
    cnt = -1
elif K==1:
    cnt = 0
else:
    cnt = 0
    for i in range(K):
        cnt += heapq.heappop(F[i])
    F1 = []
    for T in F:
        F1 += T
    F1 = sorted(F1)
    for i in range(K-2):
        cnt += F1[i]
if cnt<0:
    print("Impossible")
else:
    print(cnt)

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*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 unit(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    elif self.rank[x]<self.rank[y]:
      self.par[x] = y
    elif self.rank[y]<self.rank[x]:
      self.par[y] = x
    else:
      self.par[y] = x
      self.rank[x] += 1
      
  def same(self, x, y):
    return self.find(x)==self.find(y)

from collections import defaultdict
N,M,*L = map(int, open(0).read().split())
A = L[:N]
U = UnionFind(N)
for x,y in zip(*[iter(L[N:])]*2):
  U.unit(x,y)
ans = 0
rest = []
dic = defaultdict(list)
for i in range(N):
  dic[U.find(i)].append(A[i])
for k in dic.keys():
  dic[k].sort()
  ans += dic[k][0]
  rest.extend(dic[k][1:])
if N-1==M:
  print(0)
  exit()
if N<2*(N-M-1):
  print('Impossible')
  exit()

rest.sort()
remain = 2*(N-M-1)-len(dic.keys())
ans += sum(rest[:remain])
print(ans)

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

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    d = defaultdict(list)
        
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(a):
        if I[a] == a:
            return a
        else:
            I[a] = root(I[a])
            return I[a]
            
    def unite(a,b):
        pa,pb = root(a),root(b)
        ra,rb = rank[a],rank[b]
        if ra > rb:
            I[pb] = pa
        else:
            I[pa] = pb
            if ra == rb:
                rank[pb] += 1
    
    for _ in range(M):
        x,y = map(int,input().split())
        unite(x,y)
        parent = root(x)
    
    for i,num in enumerate(I):
        parent = root(num)
        heapq.heappush(d[parent],a[i])
        
    if M == N-1:
        print(0)
        exit()
    elif N < 2*(N-M-1):
        print("Impossible")
        exit()

    l = len(d.keys())
    ans = 0
    rest = []
    for use in d.values():
        ans += heapq.heappop(use)
        rest.extend(use)

    remain = 2*(N-M-1)-l
    rest.sort()
    ans += sum(rest[:remain])
    
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
from heapq import *

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            return True
        else:
            return False

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
uf = UnionFind(n)
ans = 0
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x, y)
if n < 2*(n-m-1):
    print('Impossible')
    exit(0)
if m == n-1:
    print(0)
    exit(0)
tree = {}
pq = []
heapify(pq)
for i in range(n):
    p = uf.find(i)
    if not p in tree.keys():
        ans += a[i]
        tree[p] = a[i]
    else:
        if tree[p] <= a[i]:
            heappush(pq, a[i])
        else:
            ans += a[i] - tree[p]
            heappush(pq, tree[p])
            tree[p] = a[i]
l = len(tree)

for _ in range(2*(n-m-1) - l):
    ans += heappop(pq)
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))






class UF(object):
    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:
            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
            self.size[x] += self.size[y]

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

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

N,M = LI()
a = LI()
x,y = LIR(M,2)

uf = UF(N)
for i in range(M):
    uf.union(x[i],y[i])

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

for g in d.values():
    g.sort(reverse=True)

if 2*(len(d)-1) > N:
    print('Impossible')
else:
    if len(d) == 1:
        print(0)
        exit()
    ans = 0
    num = 0
    for gr in d.values():
        ans += gr.pop()
        num += 1
    left = []
    for gr in d.values():
        left.extend(gr)
    left.sort()
    for i in range(2*(len(d)-1)-num):
        ans += left[i]
    print(ans)

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

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    d = defaultdict(list)
        
    I = [i for i in range(N)]
    rank = [1 for _ in range(N)]
    def root(a):
        if I[a] == a:
            return a
        else:
            I[a] = root(I[a])
            return I[a]
            
    def unite(a,b):
        pa,pb = root(a),root(b)
        ra,rb = rank[a],rank[b]
        if ra > rb:
            I[pb] = pa
        else:
            I[pa] = pb
            if ra == rb:
                rank[pb] += 1
    
    for _ in range(M):
        x,y = map(int,input().split())
        unite(x,y)
        parent = root(x)
    
    for i,num in enumerate(I):
        parent = root(num)
        heapq.heappush(d[parent],a[i])
        
    if M == N-1:
        print(0)
        exit()
    elif N < 2*(N-M-1):
        print("Impossible")
        exit()

    l = len(d.keys())
    ans = 0
    rest = []
    for use in d.values():
        ans += heapq.heappop(use)
        rest.extend(use)

    remain = 2*(N-M-1)-l
    rest.sort()
    ans += sum(rest[:remain])
    
    print(ans)
    
if __name__ == "__main__":
    main()