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
sys.setrecursionlimit(10 ** 7)
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)
XY = [[int(x) for x in input().split()] for _ in range(M)]

if M>0:
    X,Y = zip(*XY)
else:
    X,Y = [],[]
n_comp,comp = connected_components(csr_matrix(([1]*M,(X,Y)),(N,N)))

i = np.lexsort((A,comp))
A = A[i]; comp = comp[i]

i = np.concatenate([[0],np.where(comp[1:] != comp[:-1])[0]+1])

cost = A[i].sum()
A = np.delete(A,i)
rest = 2 * (n_comp-1) - len(i)
if n_comp == 1:
    print(0)
elif rest > len(A):
    print('Impossible')
else:
    A.sort()
    cost += A[:rest].sum()
    print(cost)

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        
        if self._ranks[x] > self._ranks[y]:
            
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
XY = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

uf = UnionFind(size=N)
for x, y in XY:
    uf.unite(x, y)


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

A = np.array(A, dtype=int)
idx = A.argsort()

ans = 0
cnt = 0
used_n = np.zeros(N, dtype=bool)
used_root = np.zeros(N, dtype=bool)
for i in idx:
    if not used_root[uf.root(i)]:
        used_root[uf.root(i)] = True
        used_n[i] = True
        ans += A[i]
        cnt += 1

for i in idx:
    if not used_n[i]:
        ans += A[i]
        cnt += 1
    if cnt >= (N - M - 1) * 2:
        break
print(ans)

Solution (Python):
from collections import deque
import sys


def dfs(adj, start, visited, cost):
    que = deque()
    que.append(start)
    cost_list = []
    while que:
        v = que.pop()
        visited[v] = 1
        cost_list.append(cost[v])
        for u in adj[v]:
            if visited[u] == 0:
                que.append(u)
    visited_ret = visited
    return sorted(cost_list), visited_ret


N, M = map(int, input().split())
cost = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

visited = [0] * N
cost_lists = []
for i in range(N):
    if visited[i] == 0:
        cost_list, visited = dfs(adj, i, visited, cost)
        cost_lists.append(cost_list)

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

ans = 0
pool = []
for i, cost_list in enumerate(cost_lists):
    for j, cost in enumerate(cost_list):
        if j == 0:
            ans += cost
        else:
            pool.append(cost)
pool.sort()
for i in range(len(cost_lists) - 2):
    if i < len(pool):
        ans += pool[i]
    else:
        print('Impossible')
        sys.exit()
print(ans)

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

uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

for i in range(m):
    x,y = map(int, input().split())
    unite(x,y)
if m == n-1:
    print(0)
elif (n-m-1)*2 > n:
    print("Impossible")
else:
    d = defaultdict(list)
    for i in range(n):
        heappush(d[root(i)], a[i])
    cnt = (n-m-1)*2
    ans = 0
    heap = []
    for value in d.values():
        ans += heappop(value)
        cnt -= 1
        while value:
            heappush(heap, heappop(value))
    for _ in range(cnt):
        ans += heappop(heap)
    print(ans)

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


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    uft = UnionFindTree(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uft.unite(x, y)
    groups = uft.groups()
    if len(groups) == 1:
        print(0)
        return
    ans = 0
    h = []
    for g in groups:
        costs = [A[x] for x in g]
        costs.sort()
        ans += costs[0]
        for cost in costs[1:]:
            heappush(h, cost)
    if len(groups) == 2 and N == 2:
        print(ans)
        return
    if len(h) < len(groups)-2:
        print("Impossible")
        return
    for _ in range(len(groups)-2):
        ans += heappop(h)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import groupby


N, M = map(int, input().split())
a = list(map(int, input().split()))
x, y = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

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




uft = UnionFindTree(N - 1)
for X, Y in zip(x, y):
    uft.union(X, Y)

C = [
    sorted(c, key=lambda i: a[i])
    for _, c in groupby(
        sorted(range(N), key=uft.find),
        uft.find
    )
]

K = 2 * (len(C) - 1)
S = {c[0] for c in C}

ans = (
    'Impossible' if K > N else
    0 if K == 0 else
    sum(a[s] for s in S) +
    sum(sorted(a[i] for i in range(N) if i not in S)[:(K - len(C))])
)


print(ans)

Solution (Python):
import collections, heapq
N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]
G = collections.defaultdict(list)
for x, y in XY:
    G[x] += [y]
    G[y] += [x]
B = sorted([v, i] for i, v in enumerate(A))
visited = [0] * N
ans = 0
H = []
t = 0
for b in B:
    v, i = b
    if not visited[i]:
        visited[i] = 1
        ans += v
        q = G[i]
        t += 1
        while q:
            i = q.pop()
            if not visited[i]:
                visited[i] = 1
                heapq.heappush(H, [A[i], i])
                q += G[i]
if len(H) < t - 2:
    print('Impossible')
    exit()
elif t == 1:
    print(0)
    exit()
for _ in range(t - 2):
    v, i = heapq.heappop(H)
    ans += v
print(ans)

Solution (Python):
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[y] = bx
    A[by] = bx



import heapq
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    V = [ i for i in range(N)]
    q = []
    for _ in range(M):
        x, y = map( int, input().split())
        union(V, x, y)
    C = [0]*N
    T = [ [] for _ in range(N)]
    for i in range(N):
        C[find(V,i)] += 1
        heapq.heappush(T[find(V,i)], A[i])
    ans = 0
    if M == 0 and N == 1:
        print(0)
        return
    if M == 0:
        print("Impossible")
        return
    s = 0
    for i in range(N):
        if C[i] >= 2:
            if s == 0:
                q = T[i]
                heapq.heapify(q)
                s = 1
                continue
            if q:
                ans += heapq.heappop(q)
                ans += heapq.heappop(T[i])
                for a in T[i]:
                    heapq.heappush(q, a)
            else:
                print("Impossible")
                return
    for i in range(N):
        if C[i] == 1:
            if q:
                ans += heapq.heappop(q)
                ans += T[i][0]
            else:
                print("Impossible")
                return
    print(ans)
            
if __name__ == '__main__':
    main()

Solution (Python):
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[y] = bx
    A[by] = bx



import heapq
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    V = [ i for i in range(N)]
    q = []
    for _ in range(M):
        x, y = map( int, input().split())
        union(V, x, y)
    C = [0]*N
    T = [ [] for _ in range(N)]
    for i in range(N):
        C[find(V,i)] += 1
        heapq.heappush(T[find(V,i)], A[i])
    ans = 0
    if M == 0 and N == 1:
        print(0)
        return
    if M == 0:
        print("Impossible")
        return
    s = 0
    for i in range(N):
        if C[i] >= 2:
            if s == 0:
                q = T[i]
                heapq.heapify(q)
                s = 1
                continue
            if q:
                ans += heapq.heappop(q)
                ans += heapq.heappop(T[i])
                for a in T[i]:
                    heapq.heappush(q, a)
            else:
                print("Impossible")
                return
    for i in range(N):
        if C[i] == 1:
            if q:
                ans += heapq.heappop(q)
                ans += T[i][0]
            else:
                print("Impossible")
                return
    print(ans)
            
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

def input():
    return sys.stdin.readline()[:-1]

n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
k = 0

pqs = []
edge = [[] for _ in range(n)]
for i in range(m):
    x, y = [int(item) for item in input().split()]
    edge[x].append(y)
    edge[y].append(x)

def dfs(n):
    kind[n] = k
    heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] == -1:
            dfs(item)

kind = [-1] * n
for i, item in enumerate(kind):
    if item == -1:
        pqs.append([])
        dfs(i)
        k += 1

if k == 1:
    print(0)
    exit()
    
ans = 0
for i in range(k):
    val = heappop(pqs[i])
    ans += val
pqs = [flatten for inner in pqs for flatten in inner] 
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

Solution (Python):
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

def input():
    return sys.stdin.readline()[:-1]

n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
k = 0

pqs = []
edge = [[] for _ in range(n)]
for i in range(m):
    x, y = [int(item) for item in input().split()]
    edge[x].append(y)
    edge[y].append(x)

def dfs(n):
    kind[n] = k
    heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] == -1:
            dfs(item)

kind = [-1] * n
for i, item in enumerate(kind):
    if item == -1:
        pqs.append([])
        dfs(i)
        k += 1

if k == 1:
    print(0)
    exit()
    
ans = 0
for i in range(k):
    val = heappop(pqs[i])
    ans += val
pqs = [flatten for inner in pqs for flatten in inner] 
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

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

def input():
	return sys.stdin.readline()[:-1]

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

root = [-1 for _ in range(n)]
is_minimum = [False for _ in range(n)]

def dfs(x, r):
	global mi, mi_ind
	if a[x] < mi:
		mi = a[x]
		mi_ind = x
	for v in adj[x]:
		if root[v] < 0:
			root[v] = r
			dfs(v, r)
	return mi_ind

for i in range(n):
	if root[i] < 0:
		mi, mi_ind = 10**10, -1
		root[i] = i
		is_minimum[dfs(i, i)] = True

con_num = len(set(root))

if (con_num-1) * 2 > n:
	print("Impossible")
	sys.exit()
elif con_num == 1:
	print(0)
	sys.exit()
ans = sum([a[i] for i in range(n) if is_minimum[i]])
ans += sum(sorted([a[i] for i in range(n) if not is_minimum[i]])[:con_num-2])
print(ans)

Solution (Python):

import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


if M == N-1:
    print(0)
elif N < 2*(N-M-1):
    print("Impossible")
else:
    cost = 0
    cnt = 0
    for l in Un.get_parents():
        cost += heapq.heappop(Un.costs[l])
        cnt += len(Un.costs[l])

    remain_l = []
    for l in Un.get_parents():
        for v in Un.costs[l]:
            heapq.heappush(remain_l, v)
    for _ in range(2*(N-M-1)-len(Un.get_parents())):
        cost += heapq.heappop(remain_l)
    print(cost)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
if N - 1 == M:
    print(0)
    exit()
if N < 2 * (N - M - 1):
    print('Impossible')
    exit()


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


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


A = list(map(int, input().split()))
G = [[] for i in range(N)]
X, Y = [], []
for i in range(M):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    unite(x, y)

K = 0
D = defaultdict(list)
for i in range(N):
    k = find(i)
    if not D[k]:
        K += 1
    D[k].append((A[i], i))

ans = 0
used = [0] * N
for v in D.values():
    s = min(v)
    ans += s[0]
    used[s[1]] = 1

T = []
for i in range(N):
    if not used[i]:
        T.append(A[i])

T = sorted(T)
ans += sum(T[:2 * (N - M - 1) - K])
print(ans)

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

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[B]>=size[C]:
        P[C]=P[B]
        size[B]+=size[C]
    else:
        P[B]=P[C]
        size[C]+=size[B]
for i in range(M):
    x,y=map(int,input().split())
    if find(x)!=find(y):
        union(x,y)
        
p=[]
for i in range(N):
    p.append([A[i],find(P[i])])

p.sort()
ANS1=[]
ANS2=[]
d={}
for i in range(N):
    if p[i][1] in d:
        ANS2.append(p[i][0])
    else:
        d[p[i][1]]=1
        ANS1.append(p[i][0])

if (len(ANS1)+len(ANS1)-2)>N:
    print("Impossible")
elif len(ANS1)==1:
    print(0)
else:
    ANS=sum(ANS1)+sum(ANS2[:len(ANS1)-2])
    print(ANS)

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

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[B]>=size[C]:
        P[C]=P[B]
        size[B]+=size[C]
    else:
        P[B]=P[C]
        size[C]+=size[B]
for i in range(M):
    x,y=map(int,input().split())
    if find(x)!=find(y):
        union(x,y)
        
p=[]
for i in range(N):
    p.append([A[i],find(P[i])])

p.sort()
ANS1=[]
ANS2=[]
d={}
for i in range(N):
    if p[i][1] in d:
        ANS2.append(p[i][0])
    else:
        d[p[i][1]]=1
        ANS1.append(p[i][0])

if (len(ANS1)+len(ANS1)-2)>N:
    print("Impossible")
elif len(ANS1)==1:
    print(0)
else:
    ANS=sum(ANS1)+sum(ANS2[:len(ANS1)-2])
    print(ANS)

Solution (Python):

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

class Uf:
    def __init__(self, N, mins):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
        self.mins = mins
        self.amins = list(range(N))

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0

            if self.mins[v] > self.mins[u]:
                self.mins[v] = self.mins[u]
                self.amins[v] = self.amins[u]
            self.mins[u] = -1
            self.amins[u] = -1
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.mins[u] > self.mins[v]:
                self.mins[u] = self.mins[v]
                self.amins[u] = self.amins[v]
            self.mins[v] = -1
            self.amins[v] = -1

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

    def min(self, x):
        return self.mins[self.root(x)]

uf = Uf(N, A.copy())

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


mins = [x for x in uf.mins if x != -1]
amins = set([x for x in uf.amins if x != -1])
ans = sum(mins)
A = [a for i, a in enumerate(A) if i not in amins]
A.sort()
ntrees = len(mins)
if ntrees == 1:
    print(0)
    exit()
if ntrees * 2 - 2 > N:
    print("Impossible")
    exit()
ans += sum(A[:ntrees - 2])
print(ans)

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

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

    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

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

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

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

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

for i in D:
    D[i] = sorted(D[i])

ans = 0
Q = []

x = len(D)
for i in D:
    if len(D[i]) == 1:
        ans += D[i][0]
    else:
        ans += D[i][0]
        m = len(D[i])
        for j in range(1, m):
            heappush(Q, D[i][j])

if len(D) == 1:
    print(0)
else:
    if N >= 2 * len(D) - 2:
        for i in range(len(D) - 2):
            x = heappop(Q)
            ans += x
        print(ans)
    else:
        print("Impossible")

Solution (Python):
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=[int(i) for i in input().split()]
x=[0 for i in range(M)]
y=[0 for i in range(M)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(M):
    unite(x[i],y[i])
A=[find(i) for i in range(N)]
K=0
D=dict()
for i in range(N):
    if A[i] in D:
        D[A[i]].append((a[i],i))
    else:
        D[A[i]]=[(a[i],i)]
        K+=1
ans=0
used=[0 for i in range(N)]
for i in D:
    seq=min(D[i])
    ans+=seq[0]
    used[seq[1]]=1
q=[]
for i in range(N):
    if used[i]==0:
        heapq.heappush(q,(a[i],i))
for _ in range(2*(N-M-1)-K):
    s,t=heapq.heappop(q)
    ans+=s
print(ans)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
if N-1==M:
  print(0)
  exit()
A=[int(a) for a in input().split()]
G=[[] for i in range(N)]
inf=float("inf")
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)
Tree=[-1]*N

def BFS(x,n):
  global Tree
  stack=deque([x])
  while stack:
    a=stack.popleft()
    Tree[a]=n
    for b in G[a]:
      if Tree[b]<0:
        stack.append(b)
n=0
for i in range(N):
  if Tree[i]<0:
    BFS(i,n)
    n+=1
    
P=[inf]*n
for i in range(N):
  P[Tree[i]]=min(P[Tree[i]],A[i])
P.sort()
ans=sum(P)
P.append(inf)
k=0
A.sort()
for i in range(N):
  if A[i]==P[k]:
    A[i]=inf
    k+=1
A.sort()
if 2*(N-M-1)-n>=N or n>2*(N-M-1) or N-2*(N-M-1)<0:
  print("Impossible")
  exit()
for i in range(2*(N-M-1)-n):
  ans+=A[i]
if ans!=inf:
  print(ans)

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


def solve():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))

    if M == N - 1:
        ans = 0
    elif 2 * (N - M - 1) > N:
        ans = 'Impossible'
    else:
        g2i = [[i] for i in range(N)]
        i2g = list(range(N))

        def merge(ia, ib):
            
            if len(g2i[i2g[ia]]) < len(g2i[i2g[ib]]): ia, ib = ib, ia
            ga, gb = i2g[ia], i2g[ib]
            for j in g2i[gb]: i2g[j] = ga
            g2i[ga].extend(g2i[gb])
            g2i[gb] = []

        for _ in range(M):
            tx, ty = map(int, input().split())
            merge(tx, ty)

        ans = 0
        need = 2 * (N - M - 1)
        rest = []
        for gi in range(len(g2i)):
            t = []
            for i in g2i[gi]:
                t.append(a[i])
            if not t: continue
            heapify(t)
            ans += heappop(t)
            need -= 1
            rest += t
        ans += sum(sorted(rest)[:need])

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    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):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):
        return self.find(x)==self.find(y)
from collections import defaultdict
from heapq import heapify,heappop
import sys
N,M = map(int,input().split())
tree = Unionfindtree(N)
A = [int(i) for i in input().split()]
table=[]
for i in range(M):
    x,y=map(int,input().split())
    tree.union(x,y)

dd=defaultdict(list)
for i in range(N):
    dd[tree.find(i)].append(A[i])
ans=0
g=0
for s in dd.keys():
    heapify(dd[s])
    ans+=heappop(dd[s])
    g+=1
if g==1:
    print(0)
    sys.exit()
if g==2:
    print(ans)
    sys.exit()
L=[]
for s in dd.values():
    L+=list(s)
L.sort()
if len(L)<g-2:
    print('Impossible')
    sys.exit()

ans+=sum(L[:g-2])
print(ans)

Solution (Python):
N, M = map(int, input().split())
a = list(map(int, input().split()))
par = list(range(N))

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

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

for _ in range(M):
    unite(*map(int, input().split()))

group = {i: [] for i in range(N)}
for i in range(N):
    group[root(i)].append((a[i], i))
ans = 0
cnt = 2 * (N - M - 1)
if N < cnt:
    print('Impossible')
    exit()
elif cnt == 0:
    print(0)
    exit()

visited = set()
for g in group.values():
    if g:
        c, i = min(g)
        ans += c
        cnt -= 1
        visited.add(i)

for v, i in sorted((v, i) for i, v in enumerate(a)):
    if cnt > 0 and i not in visited:
        ans += v
        visited.add(i)
        cnt -= 1
print(ans)

Solution (Python):
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
par,rank,b,t = [i for i in range(n)],[0 for i in range(n)],[],n-m-1
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
for _ in range(m):
	x,y = (int(i) for i in input().split())
	unite(x,y)
for i in range(n): par[i] = root(par[i])
if n<2*t: ans = "Impossible"
elif t==0: ans = 0
else:
	for i in range(n): b.append((a[i],par[i]))
	ans,b,v,w = 0,sorted(b),[1]*n,n-m-2
	for i,j in b:
		if v[j]: v[j],ans = 0,ans+i
		elif w: w,ans = w-1,ans+i
print(ans)