Vova promised himself that he would never play computer games... But recently Firestorm — a well-known game developing company — published their newest game, World of Farcraft, and it became really popular. Of course, Vova started playing it.

Now he tries to solve a quest. The task is to come to a settlement named Overcity and spread a rumor in it.

Vova knows that there are n characters in Overcity. Some characters are friends to each other, and they share information they got. Also Vova knows that he can bribe each character so he or she starts spreading the rumor; i-th character wants c_{i} gold in exchange for spreading the rumor. When a character hears the rumor, he tells it to all his friends, and they start spreading the rumor to their friends (for free), and so on.

The quest is finished when all n characters know the rumor. What is the minimum amount of gold Vova needs to spend in order to finish the quest?

Take a look at the notes if you think you haven't understood the problem completely.


-----Input-----

The first line contains two integer numbers n and m (1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5) — the number of characters in Overcity and the number of pairs of friends.

The second line contains n integer numbers c_{i} (0 ≤ c_{i} ≤ 10^9) — the amount of gold i-th character asks to start spreading the rumor.

Then m lines follow, each containing a pair of numbers (x_{i}, y_{i}) which represent that characters x_{i} and y_{i} are friends (1 ≤ x_{i}, y_{i} ≤ n, x_{i} ≠ y_{i}). It is guaranteed that each pair is listed at most once.


-----Output-----

Print one number — the minimum amount of gold Vova has to spend in order to finish the quest.


-----Examples-----
Input
5 2
2 5 3 4 8
1 4
4 5

Output
10

Input
10 0
1 2 3 4 5 6 7 8 9 10

Output
55

Input
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10

Output
15



-----Note-----

In the first example the best decision is to bribe the first character (he will spread the rumor to fourth character, and the fourth one will spread it to fifth). Also Vova has to bribe the second and the third characters, so they know the rumor.

In the second example Vova has to bribe everyone.

In the third example the optimal decision is to bribe the first, the third, the fifth, the seventh and the ninth characters.

Difficulty: interview

Starter code:

Solutions:
#python3
# utf-8

nodes_nr, edges_nr = (int(x) for x in input().split())
node_idx___cost = [int(x) for x in input().split()]
node_idx___neigh_idxes = [[] for x in range(nodes_nr)]
for _ in range(edges_nr):
    node1_idx, node2_idx = (int(x) - 1 for x in input().split())
    node_idx___neigh_idxes[node1_idx].append(node2_idx)
    node_idx___neigh_idxes[node2_idx].append(node1_idx)

node_idx___is_visited = [False for x in range(nodes_nr)]

ans = 0
for node_idx in range(nodes_nr):
    if node_idx___is_visited[node_idx]:
        continue
    stack = [node_idx]
    node_idx___is_visited[node_idx] = True
    cheapest_cost = node_idx___cost[node_idx]
    while stack:
        curr_node_idx = stack.pop()
        for neigh_idx in node_idx___neigh_idxes[curr_node_idx]:
            if node_idx___is_visited[neigh_idx]:
                continue
            stack.append(neigh_idx)
            cheapest_cost = min(cheapest_cost, node_idx___cost[neigh_idx])
            node_idx___is_visited[neigh_idx] = True
    ans += cheapest_cost
print(ans)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2017/11/23 23:13

"""

N, M = list(map(int, input().split()))
cost = [0] + [int(x) for x in input().split()]
#
# N, M = random.randint(1, 10**5), random.randint(0, 10**5)
# cost = [0] + [random.randint(0, 10**9) for _ in range(N)]

G = collections.defaultdict(list)

for i in range(M):
    a, b = list(map(int, input().split()))
    # a, b = random.randint(1, N), random.randint(1, N)
    G[a].append(b)
    G[b].append(a)


group = [0] * (N+1)
gi = 1

# def dfs(u, fa, gi):
#     group[u] = gi
#     for v in G[u]:
#         if v != fa and group[v] == 0:
#             dfs(v, u, gi)

def makeGroup(u, gi):
    q = [u]
    while q:
        u = q.pop()
        group[u] = gi
        for v in G[u]:
            if group[v] == 0:
                q.append(v)


for i in range(1, N+1):
    if not group[i]:
        gi += 1
        makeGroup(i, gi)

for i in range(1, N+1):
    if group[i] == 0:
        gi += 1
        group[i] = gi

minCost = {}
for i in range(1, N+1):
    g = group[i]
    c = cost[i]
    if g not in minCost:
        minCost[g] = c
    else:
        minCost[g] = min(minCost[g], c)

print(sum(list(minCost.values()) or [0]))





from collections import deque

start = list(map(int, (input().strip().split())))
cost = list(map(int, (input().strip().split())))
dp = dict()
for _ in range(start[1]):
    k = list(map(int, (input().strip().split())))
    if k[0] - 1 not in dp:
        dp[k[0] - 1] = dict()
    if k[1] - 1 not in dp:
        dp[k[1] - 1] = dict()
    dp[k[0] - 1][k[1] - 1] = 0
    dp[k[1] - 1][k[0] - 1] = 0

counted = dict()
answer = 0
for index, value in enumerate(cost):
    if index not in dp:
        answer += value
    elif index in counted:
        continue
    else:
        now = index
        plus = value
        counted[index] = 0
        dec = deque()
        for key in dp[now]:
            dec.append(key)
        while len(dec) > 0:
            k = dec.popleft()
            if k in counted:
                continue
            plus = min(plus, cost[k])
            counted[k] = 0
            if k in dp:
                for key in dp[k]:
                    dec.append(key)
        answer += plus
print(answer)

def bfs(i):
    nonlocal p, f, v

    q = [i]
    qi = 0
    
    v[i] = 1
  
    best = p[i]

    while qi < len(q):
        j = q[qi]
        if p[j] < best:
            best = p[j]
        for k in f[j]:
            if v[k] != 1:
                q.append(k)
                v[k] = 1
        qi += 1

    return best

n, m = [int(i) for i in input().split(" ")]

p = [int(i) for i in input().split(" ")]
v = [0]*n
f = {}

for a in range(n):
    f[a] = []

for a in range(m):
    x, y = [int(i) for i in input().split(" ")]
    f[x-1].append(y-1)
    f[y-1].append(x-1)

cost = 0
for i in range(n):
    if v[i] == 0:
        cost += bfs(i)

print(cost)




from collections import defaultdict

class Graph(object):
	def __init__(self, connections, directed=False):
		self._graph = defaultdict(set)
		self._directed = directed
		self.add_connections(connections)

	def add_connections(self, connections):
		for node1, node2 in connections:
			self.add(node1, node2)

	def add(self, node1, node2):
		self._graph[node1].add(node2)
		if not self._directed:
			self._graph[node2].add(node1)

	def __str__(self):
		return '{}({})'.format(self.__class__.__name__, dict(self._graph))
	
	def __getitem__(self, index):
		return self._graph[index]

def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited
    
n, m = list(map(int, input().split()))
g = list(map(int, input().split()))
f = [list(map(int, input().split()))for _ in range(m)]
v = Graph(f)
fg = []
vi = [False]*n
for i in range(0, n):
	if vi[i]:
		continue
	cc = bfs(v, i+1)
	for e in cc:
		vi[e-1] = True
	fg.append(cc)
print(sum(min(g[e-1] for e in _g) for _g in fg))



def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited, min([prices[v] for v in visited])


n, m = list(map(int, input().split()))
prices = [0] + list(map(int, input().split()))
friendship = {x: set() for x in range(1, n+1)}
for _ in range(m):
    x, y = list(map(int, input().split()))
    friendship[x].add(y)
    friendship[y].add(x)
# print(friendship)
citizens = set(range(1, n+1))
ans = 0
while citizens:
    v = citizens.pop()
    visited, p = dfs(friendship, v)
    citizens.difference_update(visited)
    ans += p
print(ans)



from collections import deque

n,m=list(map(int,input().split()))
c=list(map(int,input().split()))
adj=[[] for _ in range(100000)]
for _ in range(m):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1
    adj[x].append(y)
    adj[y].append(x)
ans=0
used=[False]*n
for i in range(n):
    if used[i]:
        continue
    s=[c[i]]
    used[i]=True
    q=deque([])
    q.append(i)
    while len(q)>0:
        u=q.popleft()
        for j in range(len(adj[u])):
            v=adj[u][j]
            if not used[v]:
                used[v]=True
                s.append(c[v])
                q.append(v)
    ans+=min(s)
print(ans)


n, m = list(map(int, input().split()))
vs = list(map(int, input().split()))
if m == 0:
    print(sum(vs))
    return
# n = 100000
# m = n - 1
# vs = [0] * n
es = {i: [] for i in range(n)}
visited = {i: False for i in range(n)}
comps = []


# def dfs(vv, compp):
#     # nonlocal visited, es
#     if visited[vv]:
#         return
#     visited[vv] = True
#     compp.append(vv)
#     neighs = es[vv]
#     for neigh in neighs:
#         if visited[neigh] or neigh == vv:
#             continue
#         dfs(neigh, compp)


for i in range(m):
    f, t = list(map(int, input().split()))
    # f, t = i + 1, i + 2
    es[f-1].append(t-1)
    es[t-1].append(f-1)

for v in range(n):
    if visited[v]:
        continue
    comp = []
    deque = [v]
    while deque:
        v_temp = deque.pop(0)
        if visited[v_temp]:
            continue
        visited[v_temp] = True
        comp.append(v_temp)
        for neigh in es[v_temp]:
            if visited[neigh] or neigh == v_temp:
                continue
            deque.append(neigh)
    comps.append(comp)
# print(es)
res = 0
for comp in comps:
    if not comp:
        continue
    res += min(vs[i] for i in comp)

print(res)



from collections import deque

class Person:
    def __init__(self):
        self.friends = []
        self.taken = False
        self.price = 0

def fill(person):
    queue = deque([])
    queue.append(person)
    minimum = person.price

    while queue:
        p = queue.popleft()
        p.taken = True
        minimum = min(minimum, p.price)
        for f in p.friends:
            if not f.taken:
                queue.append(f)
    return minimum


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

people = [Person() for _ in range(0, N)]

prices = list(map(int, input().split()))
for i in range(0, N):
    people[i].price = prices[i]

for _ in range(0, M):
    u, v = map(int, input().split())
    people[u-1].friends.append(people[v-1])
    people[v-1].friends.append(people[u-1])

cost = 0
for p in people:
    if not p.taken:
        cost += fill(p)

print(cost)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Nov 19 07:28:11 2017

@author: fei
"""
n, m = [int(i) for i in input().split(' ')]
c = [int(i) for i in input().split(' ')]
chars = [[] for _ in range(n)]
for _ in range(m):
    p, q = [int(i) for i in input().split(' ')]
    p = p - 1
    q = q - 1
    chars[p].append(q)
    chars[q].append(p)

def dfs(i, nodes):
    if Visited[i]:
        return
    Visited[i] = True
    nodes.append(i)
    for j in chars[i]:
        dfs(j, nodes)

Visited = [False for i in range(n)]
Graph = []
C = 0
for i in range(n):
    if not Visited[i]:
        nodes = []
        nodes.append(i)
        tmp = 10000000000
        while len(nodes) > 0:
            u = nodes.pop()
            if Visited[u] == False:
                Visited[u] = True
                tmp = min(tmp, c[u])
                for j in chars[u]:
                    nodes.append(j)
        C += tmp
        Graph.append(nodes)

print(C)

import threading, sys
sys.setrecursionlimit(10 ** 9)
threading.stack_size(67108864)

def main():
    n, m = [int(x) for x in input().split()]
    c = [int(x) for x in input().split()]
    graph = {int(x) + 1:[] for x in range(n)}
    
    for i in range(m):
        ff, sf = [int(x) for x in input().split()]
        graph[ff].append(sf)
        graph[sf].append(ff)
        
    comps = {}
    cl = [-1] * n
    
    def dfs(v, c, p):
        cl[v - 1] = c
        if c not in comps:
            comps[c] = []
        comps[c].append(v)
        for i in graph[v]:
            if i != p:
                if cl[i - 1] == -1:
                    dfs(i, c, v)
    
    cc = 1
    for i in range(n):
        if cl[i] == -1:
            dfs(i + 1, cc, -1)
            cc += 1
            
    price = 0
    
    for i in comps:
        minp = 999999999999999
        for j in comps[i]:
            minp = min(c[j - 1], minp)
        price += minp
    print(price)
    
thread = threading.Thread(target=main)
thread.start()

from sys import setrecursionlimit
import threading
setrecursionlimit(10 ** 9)
threading.stack_size(67108864)

def main():
    def dfs(v,cv):
        color[v]=cv
        for u in d[v]:
            if color[u]==0:
                dfs(u,cv)

    n,m=map(int,input().split())
    c=list(map(int,input().split()))
    d={x:[] for x in range(n+1)}
    for i in range(m):
        x,y=map(int,input().split())
        d[x].append(y)
        d[y].append(x)
    color=[0]*(n+1)
    cv=1
    for i in range(1,n+1):
        if color[i]==0:
            dfs(i,cv)
            cv+=1
    s={}
    for i in range(1,n+1):
        if color[i] in s:
            s[color[i]].append(c[i-1])
        else:
            s[color[i]]=[c[i-1]]
    x=0
    for i in s:
        x+=min(s[i])
    print(x)
thread = threading.Thread(target=main)
thread.start()

from collections import defaultdict as dd
g=dd(list)
def addE(u,v):
	g[u].append(v)
	g[v].append(u)

def dfs(v):
	stck=[]
	stck.append(v)
	cost1=cost[v-1]
	visited[v]=True
	while len(stck)!=0:
		cur=stck.pop()
		for ch in g[cur]:
			if visited[ch]:
				continue
			cost1=min(cost1,cost[ch-1])
			stck.append(ch)
			visited[ch]=True
	return cost1



n,m=list(map(int,input().split()))
cost=[int(x) for x in input().split()]
visited=[False]*(n+1)
for i in range(m):
	u,v=list(map(int,input().split()))
	addE(u,v)
ans=0
for i in range(1,n+1):
	if not visited[i]:
		ans+=dfs(i)
	

for i in range(1,n+1):
	if not visited[i]:
		ans+=cost[i-1]
print(ans)


import sys, threading
sys.setrecursionlimit(100010)
threading.stack_size(67108864)

res = 0

def main():
    n,m=list(map(int,input().split()))
    c=[int(c) for c in input().split()]
    g={}
    
    
    flag=[0 for i in range(n) ]
    
     
    for i in range(n):
        g[i]=[]
        
    for i in range(m):
        p,o=list(map(int ,input().split()))
        o-=1
        p-=1
        g[o].append(p)
        g[p].append(o)
        
    def glu(v,p,k):
        nonlocal res
        if flag[v]==0:
            flag[v]=k
            for i in g[v]:
                if i!=p:
                    glu(i,v,k)
    k=1
    for i in range(n):
        l=flag[i]
        glu(i,-1,k)
        if l==0:
            k+=1
    mn={}
    for i in range(max(flag)):
        mn[i]=10**9 
    for i in range(n):
        if mn[flag[i]-1]>=c[i]:
            mn[flag[i]-1]=c[i]
    su=0
    for i in range(len(mn)):
            su+=mn[i]    
    print(su)    
    
    

thread = threading.Thread(target=main)
thread.start()


import sys, threading
sys.setrecursionlimit(100010)
threading.stack_size(67108864)
#sys.stdin=open("input.txt","r")


def main():
    n,m=list(map(int,input().split()))
    c=list(map(int,input().split()))
    edge=[[] for i in range(n)]
    for i in range(m):
        u,v=list(map(int,input().split()))
        u-=1
        v-=1
        edge[u].append(v)
        edge[v].append(u)
    flag=[0]*n

    def dfs(u,k):
        flag[u]=k;
        for v in edge[u]:
            if(flag[v]==0):
                dfs(v,k)

    cnt = 0
    for u in range(n):
        if(flag[u]==0):
            cnt+=1
            dfs(u,cnt)

    mn=[0x3f3f3f3f]*(cnt+1)

    for u in range(n):
        mn[flag[u]]=min(mn[flag[u]],c[u])

    print(sum(mn[1:]))

thread=threading.Thread(target=main)
thread.start()




from collections import defaultdict
merge_matrix = defaultdict(list)
n, m = list(map(int, input().split()))
price_list = [int(x) for x in input().split()]
summary = 0
visited = set()


def dfs(edge):
    queue = []
    visited.add(edge)
    queue.append(edge)
    lowest_cost = price_list[edge-1]
    while len(queue) > 0:
        cur_edge = queue.pop()
        for i in merge_matrix[cur_edge]:
            if i not in visited:
                lowest_cost = min(lowest_cost, price_list[i - 1])
                queue.append(i)
                visited.add(i)
    return lowest_cost


for i in range(m):
    x, y = list(map(int, input().split()))
    merge_matrix[x].append(y)
    merge_matrix[y].append(x)
for i in range(1, n+1):
    if i not in visited:
        summary += dfs(i)
for i in range(1, n+1):
    if i not in visited:
        summary += price_list[i-1]
print(summary)


R=lambda:list(map(int,input().split()))
n,m=R()
p=[i for i in range(n+1)]

def find(i):
    while p[i] != i:
        p[i] = p[p[i]]
        i = p[i]
    return i
    
c=[0]+list(R())
for _ in range(m):
    x,y=list(map(find,R()))
    if c[x]<c[y]:
        x,y=y,x
    p[x]=y
print(sum(c[i] for i in range(n+1) if p[i]==i))


n, m = map(int, input().split())
c = list(map(int, input().split()))
g = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

vs = [False for i in range(n)]
ans = 0
for i in range(n):
    if vs[i]:
        continue
    q = [i]
    vs[i] = True
    m = c[i]
    while len(q) > 0:
        v = q[0]
        del q[0]
        for u in g[v]:
            if not vs[u]:
                vs[u] = True
                q.append(u)
                m = min(m, c[u])
    ans += m
    
print(ans)

def get():
	return list(map(int, input().split()))

def dfs(i):
	v = c[i]
	q = [i]
	while q:
		j = q.pop()
		b[j] = 1
		v = min(v, c[j])
		for k in a[j]:
			if b[k] == 0:
				q.append(k)
	return v
	
n, m = get()
c = get()
a = [list() for _ in range(n)]
for _ in range(m):
	x, y = get()
	a[x-1].append(y-1)
	a[y-1].append(x-1)

b = [0] * n
ans = 0
for i in range(n):
	if b[i] == 0:
		ans += dfs(i)

print(ans)

from collections import deque


def dfs(n):
    """
    Traverse graph using DFS
    @return: minimum gold value of connected group
    """
    nonlocal visited
    minimum = -1
    queue = deque([n])
    while queue:
        node = queue.popleft()
        visited[node] = True
        if minimum == -1:
            minimum = gold[node]
        else:
            minimum = min(minimum, gold[node])
        for neighbor in adj_list[node]:
            if not visited[neighbor - 1]:
                queue.append(neighbor - 1)
    return minimum


n, m = list(map(int, input().split()))
gold = list(map(int, input().split()))
adj_list = [list() for _ in range(n)]
for _ in range(m):
    x, y = list(map(int, input().split()))
    adj_list[x - 1].append(y)
    adj_list[y - 1].append(x)
visited = [False for _ in range(n)]
total = 0
for i in range(n):
    if not visited[i]:
        total += dfs(i)
print(total)


n, m = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
fa = [0] + [i + 1 for i in range(n)]

def findFa(x):
    s = []
    while fa[x] != x:
        s.append(x)
        x = fa[x]
    for v in s:
        fa[v] = x
    return x

while m:
    u, v = list(map(int, input().split()))
    u = findFa(u)
    v = findFa(v)
    if u != v:
        fa[v] = u
        a[u] = min(a[u], a[v])
    m -= 1
res = 0
for i in range(1, n + 1):
    if findFa(i) == i:
        res += a[fa[i]]
print(res)



def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited, min([prices[v] for v in visited])


n, m = list(map(int, input().split())); ans = 0
prices = [None] + list(map(int, input().split()))
friendship = {x: set() for x in range(1, n+1)}

for _ in range(m):
    x, y = list(map(int, input().split()))
    friendship[x].add(y)
    friendship[y].add(x)
citizens = set(range(1, n+1))

while citizens:
    v = citizens.pop()
    visited, p = dfs(friendship, v)
    citizens.difference_update(visited)
    ans += p
print(ans)