It's Galactik Football time! The Galactik Football Assosiation (GFA) has announced a football tournament between all the teams of all the planets in the galaxy.

Each planet of the galaxy has a government. Some governments have a mutual agreement between them. If planet $A$ has mutual agreement with planet $B$, then there is a bidirectional spaceway between $A$ and $B$, using which anybody can go from $A$ to $B$ and vice-versa. People can use these spaceways to travel from one planet to another, if there exists a path between them using some of the spaceways.

Each planet has its own football ground. The GFA has planned the matches in such a way that a team can have a match at any of these grounds. The GFA has come across some problems in the execution of their plan. They have found out that there are many pairs of planets between which there does not exist any path, so the football team of one of those planets can't reach the other planet. They requested the corresponding governments to make a spaceway between them, but they can’t because of the absence of a mutual agreement. So the GFA suggested that they will make teleportation devices between some pairs of planets which will be used only by the football teams to travel.

But there are two types of governments in the galaxy
1. Some of the governments are greedy and they want to make money through the GFA. Each of these government has asked the GFA for a tax value which it has to pay if it wants to make a teleport ending at their planet.
2. Others want to sponsor the event, so they will give money to the GFA if they make a teleport ending at their planet. The GFA would always avoid such governments no matter what the consequences are, because these kind of governments always have some dirty plans up their sleeves.

Now, the GFA wants to make bi-directional teleports between planets such that the football teams of any planet can reach any other planet to play a football match, using spaceways between the planets and/or teleports made by the GFA.

The GFA also has financial problems and want to spend as little money as possible. They have come to you so that you can help them calculate the minimum amount of money needed to fulfil their plan.

------  Input ------
The first line of the input consists of two space separated integers - $N$ and $M$. $N$ is the number of planets and $M$ is the number of spaceways. The description of the spaceways follows. 
The next $M$ lines, each contain two space separated integers $A$ and $B$, denoting a mutual agreement and hence a spaceway to travel, between planet $A$ and planet $B$.
The next $N$ lines each contain a single integer, the integer on the $i^{th}$ line representing $C_{i}$. If $C_{i} ≥ 0$, then it represents the tax value which the GFA has to pay to the government of planet $i$ (it's a type $1$ government). If $C_{i} < 0$, then it represents the money that the $i^{th}$ government will pay to the GFA (it's a type $2$ government).

------  Output ------
Print the minimum amount needed for the GFA to fulfil their plan. If there is no way to do so, print "-1" (without quotes).

------  Constraints ------
$1 ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 10^{6}$
$0 ≤ |C| ≤ 10^{4}$
$1 ≤ A,B ≤ N$
$A \neq B$

----- Sample Input 1 ------ 
6 6
1 2
2 3
1 3
4 5
5 6
4 6
1
3
5
2
4
6
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 

----- Sample Input 2 ------ 
3 1
2 3
1
-1
-1
----- Sample Output 2 ------ 
-1
----- explanation 2 ------

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Greedy algorithms

Tree algorithms

Spanning trees

Data structures
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
class DisjointSet:

	def __init__(self, n, cost):
		self.parent = [i for i in range(n + 1)]
		self.rank = [1] * (n + 1)
		self.cost = cost
		self.visited = [0] * (n + 1)

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

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

	def populate_representatives(self, x):
		root = self.find(x)
		if 0 <= self.cost[x] < self.cost[root] or (self.cost[root] < 0 and self.cost[x] >= 0):
			self.cost[root] = self.cost[x]
(n, m) = map(int, input().strip().split())
connections = []
cost = [0] * (n + 1)
summ = 0
minimum = 100005
count = 0
not_possible = 0
for _ in range(m):
	(x, y) = map(int, input().strip().split())
	connections.append((x, y))
for _ in range(1, n + 1):
	cost[_] = int(input())
ds = DisjointSet(n, cost)
for i in connections:
	ds.union(i[0], i[1])
for _ in range(1, n + 1):
	ds.populate_representatives(_)
for i in range(1, n + 1):
	if not ds.visited[ds.parent[i]]:
		ds.visited[ds.parent[i]] = 1
		if ds.cost[ds.parent[i]] < 0:
			not_possible = 1
		summ += ds.cost[ds.parent[i]]
		minimum = min(minimum, ds.cost[ds.parent[i]])
		count += 1
if count != 1:
	if not_possible:
		print(-1)
	else:
		count = (count - 2) * minimum
		print(summ + count)
else:
	print(0)


import sys
import bisect
sys.setrecursionlimit(1000000)

def find(a):
	while dsu[a] != a:
		dsu[a] = dsu[dsu[a]]
		a = dsu[a]
	return a

def union(a, b):
	s1 = find(a)
	s2 = find(b)
	if rank[s1] > rank[s2]:
		dsu[s2] = s1
	elif rank[s2] > rank[s1]:
		dsu[s1] = s2
	else:
		rank[s1] += 1
		dsu[s2] = s1
(n, m) = map(int, input().split())
dsu = [i for i in range(n)]
rank = [0] * n
for i in range(m):
	(a, b) = map(int, input().split())
	union(a - 1, b - 1)
arr = []
for i in range(n):
	a = int(input())
	if a >= 0:
		bisect.insort(arr, [a, i])
cost = 0
for i in range(1, len(arr)):
	if find(arr[0][1]) != find(arr[i][1]):
		union(arr[0][1], arr[i][1])
		cost += arr[0][0] + arr[i][0]
s = set()
for i in range(n):
	s.add(find(i))
if len(s) == 1:
	print(cost)
else:
	print('-1')


from collections import defaultdict
MAXINT = 1000000
(n, m) = list(map(int, input().split()))
(mincost, cost) = ([], [-1])
graph = defaultdict(list)
for i in range(m):
	(a, b) = list(map(int, input().split()))
	graph[a].append(b)
	graph[b].append(a)
for i in range(n):
	c = int(input())
	if c < 0:
		c = MAXINT
	cost.append(c)
ans = 0
visited = [False] * (n + 1)

def dfs(i):
	mcost = MAXINT
	buffer = [i]
	while buffer:
		v = buffer.pop()
		mcost = min(mcost, cost[v])
		for nb in graph[v]:
			if not visited[nb]:
				visited[nb] = True
				buffer.append(nb)
	return mcost
for i in range(1, n + 1):
	if not visited[i]:
		visited[i] = True
		mincost.append(dfs(i))
(cmax, cmin) = (max(mincost), min(mincost))
if len(mincost) == 1:
	print(0)
elif cmax == MAXINT:
	print(-1)
else:
	print(sum(mincost) + (len(mincost) - 2) * cmin)


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(vi, n, ed, c, mi):
	vi[n] = True
	if c[n] >= 0:
		mi[0] = min(mi[0], c[n])
	for l in ed[n]:
		if vi[l] == False:
			dfs(vi, l, ed, c, mi)
(n, m) = [int(a) for a in input().split()]
ed = []
for l in range(n + 1):
	ed.append([])
for l in range(m):
	(u, v) = [int(a) for a in input().split()]
	ed[u].append(v)
	ed[v].append(u)
c = [0]
for l in range(n):
	c.append(int(input()))
ans = []
vi = []
for l in range(n + 1):
	vi.append(False)
co = 0
for v in range(1, n + 1):
	mi = [float('inf')]
	f = False
	if vi[v] == False:
		dfs(vi, v, ed, c, mi)
		co = co + 1
		if mi[0] == float('inf'):
			if co >= 2:
				f = True
				print(-1)
				break
			else:
				ans.append(0)
		else:
			ans.append(mi[0])
	if f:
		break
if not f:
	to = 0
	ans.sort()
	for l in range(1, len(ans)):
		to = to + ans[l] + ans[0]
	print(to)


from collections import defaultdict
import gc
gc.disable()

def find(a):
	if par[a] == a:
		return a
	else:
		par[a] = find(par[a])
		return par[a]

def union(a, b):
	(a, b) = (find(a), find(b))
	if a != b:
		if rank[a] > rank[b]:
			par[b] = a
		elif rank[b] > rank[a]:
			par[a] = b
		else:
			par[a] = b
			rank[b] += 1
changed_big_value = 10 ** 10
(n, m) = map(int, input().split())
par = [i for i in range(n + 1)]
rank = [0 for i in range(n + 1)]
cost = [-1 for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	union(u, v)
up = set()
for i in range(1, n + 1):
	c = int(input())
	j = find(i)
	up.add(j)
	if c >= 0:
		if cost[j] == -1:
			cost[j] = c
		else:
			cost[j] = min(cost[j], c)
if len(up) == 1:
	print(0)
else:
	flag = True
	for i in up:
		if cost[i] == -1:
			print(-1)
			flag = False
			break
	if flag:
		t = [cost[x] for x in up]
		t.sort()
		print(sum(t) + (len(t) - 2) * t[0])


from sys import stdin, stdout

def find(a):
	if par[a] == a:
		return a
	else:
		par[a] = find(par[a])
		return par[a]

def union(a, b):
	(a, b) = (find(a), find(b))
	if a != b:
		if rank[a] > rank[b]:
			par[b] = a
		elif rank[b] > rank[a]:
			par[a] = b
		else:
			par[a] = b
			rank[b] += 1
(n, m) = stdin.readline().strip().split(' ')
(n, m) = (int(n), int(m))
par = [i for i in range(n)]
rank = [0 for i in range(n)]
cost = [-1 for i in range(n)]
for i in range(m):
	(u, v) = stdin.readline().strip().split(' ')
	(u, v) = (int(u) - 1, int(v) - 1)
	union(u, v)
up = set()
for i in range(n):
	c = int(stdin.readline().strip())
	up.add(find(i))
	if c >= 0:
		if cost[find(i)] == -1:
			cost[find(i)] = c
		else:
			cost[find(i)] = min(cost[find(i)], c)
if len(up) == 1:
	print(0)
else:
	flag = True
	for i in up:
		if cost[i] == -1:
			print(-1)
			flag = False
			break
	if flag:
		t1 = [cost[x] for x in up]
		t1.sort()
		print(sum(t1) + (len(t1) - 2) * t1[0])


from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(100000)

class Graph:

	def __init__(self, vertices):
		self.graph = [-1 for i in range(vertices + 1)]

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

	def union(self, x, y):
		if self.graph[x] <= self.graph[y]:
			self.graph[x] += self.graph[y]
			self.graph[y] = x
		else:
			self.graph[y] += self.graph[x]
			self.graph[x] = y

	def addEdge(self, x, y):
		x = self.findParent(x)
		y = self.findParent(y)
		if x != y:
			self.union(x, y)
(n, m) = map(int, input().split())
planets = n
g = Graph(n)
cost = []
for _ in range(m):
	(a, b) = map(int, input().split())
	g.addEdge(a, b)
for i in range(n):
	c = int(input())
	index = i + 1
	if c >= 0:
		cost.append((c, index))
cost.sort()
total = 0
n = len(cost)
if n >= 2:
	e1 = cost.pop(0)
	for i in range(n - 1):
		e2 = cost[i]
		p1 = g.findParent(e1[1])
		p2 = g.findParent(e2[1])
		if p1 != p2:
			total = total + (e2[0] + e1[0])
			g.union(p1, p2)
s = set()
for i in range(1, planets + 1):
	p = g.findParent(i)
	s.add(p)
if len(s) == 1:
	print(str(total))
else:
	print('-1')


def find(child):
	if child == parents[child]:
		return parents[child]
	parents[child] = find(parents[child])
	return parents[child]

def union(root1, root2):
	(real_root1, real_root2) = (find(root1), find(root2))
	if real_root1 == real_root2:
		return
	if rank[real_root1] <= rank[real_root2]:
		parents[real_root1] = real_root2
		if rank[real_root1] == rank[real_root2]:
			rank[real_root2] += 1
	else:
		parents[real_root2] = real_root1
(n, m) = map(int, input().strip().split())
parents = list(range(n))
rank = [0 for i in range(n)]
for i in range(m):
	(root1, root2) = map(int, input().strip().split())
	union(root1 - 1, root2 - 1)
cost_dict = {}
for i in range(n):
	if i == parents[i]:
		cost_dict[i] = 10 ** 5
cost = [10 ** 5 for i in range(n)]
min_cost = 10 ** 5
for i in range(n):
	c = int(input().strip())
	if c >= 0:
		cost[i] = c
		grand_parent = find(i)
		cost_dict[grand_parent] = min(c, cost_dict[grand_parent])
		min_cost = min(c, min_cost)
possible = True
total_cost = 0
for root in cost_dict:
	cst = cost_dict[root]
	if cst == 10 ** 5 or cst > 10 ** 4:
		possible = False
		break
	else:
		total_cost += cst
if len(cost_dict) == 1:
	print(0)
elif not possible:
	print(-1)
else:
	total_cost = total_cost + (len(cost_dict) - 2) * min_cost
	print(total_cost)


def find_root(arr, n):
	while arr[n] != n:
		n = arr[n]
	return n

def union(arr, a, b, size):
	root_a = find_root(arr, a)
	root_b = find_root(arr, b)
	if root_a == root_b:
		return
	if size[root_a] < size[root_b]:
		arr[root_a] = arr[root_b]
		size[root_b] += arr[root_a]
	else:
		arr[root_b] = arr[root_a]
		size[root_a] += size[root_b]

def same_root(arr, i, cost):
	root = find_root(arr, i)
	if cost[i] < cost[root] and cost[i] > -1 or (cost[root] < 0 and cost[i] > -1):
		cost[root] = cost[i]
	arr[i] = root
(N, M) = [int(x) for x in input().split()]
size = [1] * (N + 1)
arr = [x for x in range(N + 1)]
cost = [0]
while M > 0:
	(a, b) = [int(x) for x in input().split()]
	union(arr, a, b, size)
	M -= 1
temp = N
while temp > 0:
	cost.append(int(input()))
	temp -= 1
for i in range(1, N + 1):
	same_root(arr, i, cost)
roots_dict = {}
sum = 0
cnt = 0
min = 1000000
flag = True
for i in range(1, N + 1):
	if arr[i] not in roots_dict:
		if cost[arr[i]] < 0:
			flag = False
		sum += cost[arr[i]]
		if cost[arr[i]] < min:
			min = cost[arr[i]]
		roots_dict[arr[i]] = True
		cnt += 1
if cnt == 1:
	print('0')
elif flag:
	print(sum + (cnt - 2) * min)
else:
	print('-1')


def find(l, ind):
	if l[ind] < 0:
		return (l[ind], ind)
	else:
		return find(l, l[ind])
(n, m) = map(int, input().split())
l = [-1] * (n + 1)
for x in range(m):
	(a, b) = map(int, input().split())
	a1 = find(l, a)
	b1 = find(l, b)
	if a1[1] != b1[1]:
		if a1[0] == b1[0]:
			l[a1[1]] += a1[0]
			l[b1[1]] = a1[1]
		elif a1[0] < b1[0]:
			l[a1[1]] += b1[0]
			l[b1[1]] = a1[1]
		else:
			l[b1[1]] += a1[0]
			l[a1[1]] = b1[1]
	else:
		if a != a1[1]:
			l[a] = a1[1]
		if b != a1[1]:
			l[b] = a1[1]
l1 = [0] * n
for x in range(n):
	l1[x] = int(input())
d = dict()
for x in range(1, len(l)):
	if l[x] < 0:
		d[x] = [x]
for x in range(1, len(l)):
	if l[x] > 0:
		e = find(l, l[x])
		d[e[1]].append(x)
ans = 0
global_min = 100000
if len(d) == 1:
	print(0)
else:
	for x in d:
		min_cost = 100000
		b = 0
		for y in d[x]:
			if l1[y - 1] < 0:
				continue
			if l1[y - 1] < global_min:
				global_min = l1[y - 1]
			if l1[y - 1] < min_cost:
				min_cost = l1[y - 1]
				b = 1
		if b == 0:
			ans = -1
			break
		else:
			ans += min_cost
	if b == 0:
		print(-1)
	else:
		print(ans + (len(d) - 2) * global_min)


from collections import defaultdict
visited = defaultdict(lambda : False)
(n, m) = [int(x) for x in input().split()]
cost = defaultdict()

class Graph:

	def __init__(self):
		self.neighbours = defaultdict(list)

	def addEdge(self, u, v):
		self.neighbours[u].append(v)
		self.neighbours[v].append(u)

	def BFS(self, s, n, visited):
		queue = [s]
		visited[s] = True
		mini = 10 ** 7
		while queue:
			u = queue.pop(0)
			mini = min(cost[u], mini)
			for v in self.neighbours[u]:
				if v not in visited:
					visited[v] = True
					queue.append(v)
					mini = min(cost[v], mini)
		return mini
g = Graph()
for i in range(m):
	(u, v) = [int(x) for x in input().split()]
	g.addEdge(u, v)
for i in range(1, n + 1):
	value = int(input())
	if value >= 0:
		cost[i] = value
	else:
		cost[i] = 10 ** 7
minimums = []
for i in range(1, n + 1):
	if i not in visited:
		m = g.BFS(i, n, visited)
		minimums.append(m)
l = len(minimums)
possible = True
for i in minimums:
	if i >= 10 ** 6:
		possible = False
		break
if l == 1:
	print(0)
elif not possible:
	print(-1)
else:
	global_min = min(minimums)
	ans = global_min * (l - 1) + sum(minimums) - global_min
	print(ans)


def find(a):
	if par[a] == a:
		return a
	else:
		par[a] = find(par[a])
		return par[a]

def union(a, b):
	(a, b) = (find(a), find(b))
	if a != b:
		if rank[a] > rank[b]:
			par[b] = a
		elif rank[b] > rank[a]:
			par[a] = b
		else:
			par[a] = b
			rank[b] += 1
(n, m) = map(int, input().split())
par = [i for i in range(n + 1)]
rank = [0 for i in range(n + 1)]
cost = [-1 for i in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	union(u, v)
up = set()
for i in range(1, n + 1):
	c = int(input())
	up.add(find(i))
	if c >= 0:
		if cost[find(i)] == -1:
			cost[find(i)] = c
		else:
			cost[find(i)] = min(cost[find(i)], c)
if len(up) == 1:
	print(0)
else:
	flag = True
	for i in up:
		if cost[i] == -1:
			print(-1)
			flag = False
			break
	if flag:
		t1 = [cost[x] for x in up]
		t1.sort()
		print(sum(t1) + (len(t1) - 2) * t1[0])


from collections import defaultdict
from collections import Counter
import math
import bisect

class dsu:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.size = [0] * (n + 1)

	def start(self):
		for i in range(1, n + 1):
			self.parent[i] = i

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

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u != v:
			self.parent[v] = u

	def treeinput(self, m):
		for i in range(m):
			(u, v) = map(int, input().split())
			self.union(u, v)

	def printt(self):
		print(self.parent)
MAX = 1000000007
(n, m) = map(int, input().split())
d = dsu(n)
galaxy = defaultdict(list)
for i in range(m):
	(u, v) = map(int, input().split())
	d.union(u, v)
arr = [-999]
for i in range(n):
	arr.append(int(input()))
for i in range(1, n + 1):
	galaxy[d.find(i)].append(i)
res = []
f = 1
for num in galaxy:
	mn = MAX
	for i in galaxy[num]:
		if arr[i] >= 0:
			mn = min(mn, arr[i])
	if mn == MAX:
		f = 0
		break
	res.append(mn)
if len(galaxy) == 1:
	print(0)
elif not f:
	print(-1)
else:
	(cnt, mn, sm) = (-2, MAX, 0)
	for i in res:
		mn = min(mn, i)
		cnt += 1
		sm += i
	print(mn * cnt + sm)


def find(child):
	if child == parents[child]:
		return parents[child]
	parents[child] = find(parents[child])
	return parents[child]

def union(r1, r2):
	(mr1, mr2) = (find(r1), find(r2))
	if mr1 == mr2:
		return
	if rank[mr1] <= rank[mr2]:
		parents[mr1] = mr2
		if rank[mr1] == rank[mr2]:
			rank[mr2] += 1
	else:
		parents[mr2] = mr1
(n, m) = map(int, input().split())
parents = list(range(n))
rank = [0 for i in range(n)]
for i in range(m):
	(r1, r2) = map(int, input().strip().split())
	union(r1 - 1, r2 - 1)
cost_dict = {}
for i in range(n):
	if i == parents[i]:
		cost_dict[i] = 10 ** 5
cost = [10 ** 5 for i in range(n)]
min_cost = 10 ** 5
for i in range(n):
	c = int(input().strip())
	if c >= 0:
		cost[i] = c
		grand_parent = find(i)
		cost_dict[grand_parent] = min(c, cost_dict[grand_parent])
		min_cost = min(c, min_cost)
possible = True
total_cost = 0
for r in cost_dict:
	cst = cost_dict[r]
	if cst == 10 ** 5 or cst > 10 ** 4:
		possible = False
		break
	else:
		total_cost += cst
if len(cost_dict) == 1:
	print(0)
elif not possible:
	print(-1)
else:
	total_cost = total_cost + (len(cost_dict) - 2) * min_cost
	print(total_cost)


def get_root(i, root):
	if root[i] == i:
		return i
	return get_root(root[i], root)
(n, m) = map(int, input().split())
(edges, cost) = ([], [0])
root = list((i for i in range(n + 1)))
for i in range(m):
	edges.append(tuple(map(int, input().split())))
for i in range(n):
	cost.append(int(input()))
for edge in edges:
	(x, y, xroot, yroot) = (edge[0], edge[1], get_root(edge[0], root), get_root(edge[1], root))
	if xroot != yroot:
		if cost[xroot] >= 0 and cost[yroot] >= 0:
			if cost[xroot] <= cost[yroot]:
				root[y] = xroot
				root[yroot] = xroot
			else:
				root[x] = yroot
				root[xroot] = yroot
		elif cost[xroot] <= 0 and cost[yroot] <= 0:
			root[y] = xroot
			root[yroot] = xroot
		elif cost[xroot] < 0:
			root[x] = yroot
			root[xroot] = yroot
		else:
			root[y] = xroot
			root[yroot] = xroot
for i in range(1, n + 1):
	root[i] = get_root(i, root)
d = {}
for i in range(1, n + 1):
	d[root[i]] = cost[root[i]]
d = list(d.values())
minn = min(d)
if minn < 0 and len(d) > 1:
	print(-1)
else:
	print(sum(d) + (len(d) - 2) * min(d))


from collections import defaultdict

def find(x):
	to_compress = []
	while parents[x] != x:
		to_compress.append(x)
		x = parents[x]
	for i in to_compress:
		parents[i] = x
	return x

def merge(x, y):
	if ranks[x] >= ranks[y]:
		parents[find(y)] = find(x)
		ranks[find(x)] += 1
	elif ranks[x] < ranks[y]:
		parents[find(x)] = find(y)
		ranks[find(y)] += 1
(n, m) = map(int, input().split())
parents = [i for i in range(n)]
ranks = [0 for i in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	merge(a - 1, b - 1)
costs = []
for _ in range(n):
	val = int(input())
	costs.append(val)
groups = defaultdict(list)
for i in range(n):
	root = find(i)
	groups[root].append(costs[i])
min_costs_per_group = []
for i in groups.values():
	useful_govts = [x for x in i if x >= 0]
	if len(useful_govts) == 0:
		min_costs_per_group.append(-1)
		break
	min_costs_per_group.append(min(useful_govts))
if len(groups.keys()) == 1:
	print(0)
elif min_costs_per_group[-1] == -1:
	print(-1)
else:
	n_teleports = len(min_costs_per_group)
	mn = min(min_costs_per_group)
	print((n_teleports - 1) * mn + sum(min_costs_per_group) - mn)


from sys import stdin, stdout

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

def union(parent, u, v):
	(u, v) = (find(parent, u), find(parent, v))
	if u != v:
		if rank[u] > rank[v]:
			parent[v] = u
		elif rank[u] < rank[v]:
			parent[u] = v
		else:
			parent[u] = v
			rank[v] += 1
(n, m) = stdin.readline().strip().split(' ')
(n, m) = (int(n), int(m))
parent = [i for i in range(n)]
rank = [0] * n
choice = [-1 for i in range(n)]
for _ in range(m):
	(u, v) = stdin.readline().strip().split(' ')
	(u, v) = (int(u) - 1, int(v) - 1)
	union(parent, u, v)
s = set()
for i in range(n):
	c = int(stdin.readline().strip())
	s.add(find(parent, i))
	if c >= 0:
		if choice[find(parent, i)] == -1:
			choice[find(parent, i)] = c
		else:
			choice[find(parent, i)] = min(choice[find(parent, i)], c)
if len(s) == 1:
	print(0)
else:
	f = 0
	for i in s:
		if choice[i] == -1:
			print(-1)
			f = 1
			break
	if f == 0:
		t = [choice[x] for x in s]
		t.sort()
		print(sum(t) + (len(t) - 2) * t[0])


from sys import stdin

class Node:

	def __init__(self, data, price):
		self.data = data
		self.rank = 0
		self.networkPrice = price
		self.parent = self

def find_root(node):
	if node != node.parent:
		node.parent = find_root(node.parent)
		return node.parent
	return node.parent

def calculate_price(parent_1, parent_2):
	if parent_2.networkPrice < parent_1.networkPrice:
		if parent_2.networkPrice >= 0:
			return parent_2.networkPrice
		else:
			return parent_1.networkPrice
	elif parent_1.networkPrice >= 0:
		return parent_1.networkPrice
	else:
		return parent_2.networkPrice

def union(node_1, node_2):
	(parent_1, parent_2) = (find_root(node_1), find_root(node_2))
	min_price = calculate_price(parent_1, parent_2)
	if parent_1 == parent_2:
		return
	if parent_1.rank > parent_2.rank:
		parent_2.parent = parent_1
		parent_1.networkPrice = min_price
	else:
		parent_1.parent = parent_2
		parent_2.networkPrice = min_price
		if parent_1.rank == parent_2.rank:
			parent_2.rank += 1
(N, M) = map(int, stdin.readline().strip().split(' '))
queries = []
for i in range(M):
	queries.append(tuple(map(int, stdin.readline().strip().split(' '))))
prices = []
for i in range(N):
	prices.append(int(stdin.readline()))
vertex = [Node(i, j) for (i, j) in zip(range(1, N + 1), prices)]
for i in queries:
	union(vertex[i[0] - 1], vertex[i[1] - 1])
usage_dict = {}
for i in range(1, N + 1):
	usage_dict[i] = False
sum = 0
possible = True
min_cost = 10 ** 5
countDict = {}
for i in vertex:
	networkRoot = find_root(i)
	if networkRoot.data not in countDict:
		countDict[networkRoot.data] = True
	if networkRoot.networkPrice < 0:
		possible = False
		break
	if usage_dict[networkRoot.data] == False and networkRoot.networkPrice >= 0:
		if min_cost > networkRoot.networkPrice:
			min_cost = networkRoot.networkPrice
		sum += networkRoot.networkPrice
		usage_dict[networkRoot.data] = True
count = 0
for i in countDict:
	count += 1
if count == 1:
	print('0')
elif not possible:
	print('-1')
else:
	print(sum + (count - 2) * min_cost)


from collections import defaultdict
from collections import Counter
import sys, threading
sys.setrecursionlimit(5 * 10 ** 5)
threading.stack_size(10 ** 8)
MAX = 1000000007

class dsu:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.size = [0] * (n + 1)

	def start(self):
		for i in range(1, n + 1):
			self.parent[i] = i

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

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u != v:
			self.parent[v] = u

	def treeinput(self, m):
		for i in range(m):
			(u, v) = map(int, input().split())
			self.union(u, v)

	def printt(self):
		print(self.parent)

def main():
	(n, m) = map(int, input().split())
	d = dsu(n)
	galaxy = defaultdict(list)
	for i in range(m):
		(u, v) = map(int, input().split())
		d.union(u, v)
	arr = [-999]
	for i in range(n):
		arr.append(int(input()))
	for i in range(1, n + 1):
		galaxy[d.find(i)].append(i)
	res = []
	f = 1
	for num in galaxy:
		mn = MAX
		for i in galaxy[num]:
			if arr[i] >= 0:
				mn = min(mn, arr[i])
		if mn == MAX:
			f = 0
			break
		res.append(mn)
	if len(galaxy) == 1:
		print(0)
	elif not f:
		print(-1)
	else:
		(cnt, mn, sm) = (-2, MAX, 0)
		for i in res:
			mn = min(mn, i)
			cnt += 1
			sm += i
		print(mn * cnt + sm)
t = threading.Thread(target=main)
t.start()
t.join()