A club plans to hold a party and will invite some of its $n$ members. The $n$ members are identified by the numbers $1, 2, \dots, n$. If member $i$ is not invited, the party will gain an unhappiness value of $a_i$.

There are $m$ pairs of friends among the $n$ members. As per tradition, if both people from a friend pair are invited, they will share a cake at the party. The total number of cakes eaten will be equal to the number of pairs of friends such that both members have been invited.

However, the club's oven can only cook two cakes at a time. So, the club demands that the total number of cakes eaten is an even number.

What is the minimum possible total unhappiness value of the party, respecting the constraint that the total number of cakes eaten is even?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \leq 10^5$, $0 \leq m \leq \min(10^5,\frac{n(n-1)}{2})$) — the number of club members and pairs of friends.

The second line of each test case contains $n$ integers $a_1,a_2, \dots,a_n$ ($0 \leq a_i \leq 10^4$) — the unhappiness value array.

Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \leq x,y \leq n$, $x \neq y$) indicating that $x$ and $y$ are friends. Each unordered pair $(x,y)$ appears at most once in each test case.

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $10^5$.


-----Output-----

For each test case, print a line containing a single integer – the minimum possible unhappiness value of a valid party.


-----Examples-----

Input
4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1
Output
0
2
3
2


-----Note-----

In the first test case, all members can be invited. So the unhappiness value is $0$.

In the second test case, the following options are possible:

invite $1$ and $2$ ($0$ cakes eaten, unhappiness value equal to $3$);

invite $2$ and $3$ ($0$ cakes eaten, unhappiness value equal to $2$);

invite only $1$ ($0$ cakes eaten, unhappiness value equal to $4$);

invite only $2$ ($0$ cakes eaten, unhappiness value equal to $5$);

invite only $3$ ($0$ cakes eaten, unhappiness value equal to $3$);

invite nobody ($0$ cakes eaten, unhappiness value equal to $6$).

The minimum unhappiness value is achieved by inviting $2$ and $3$.

In the third test case, inviting members $3,4,5$ generates a valid party with the minimum possible unhappiness value.

Source: codeforces | Difficulty: EASY
Tags: Graph algorithms

Complete search


Solutions:
import collections
import sys

class Solver(collections.namedtuple('Solver', ('n', 'm', 'penalties', 'degrees', 'edges'))):

	@classmethod
	def read(cls, fin):
		(n, m) = map(int, fin.readline().split())
		penalties = [0]
		penalties.extend(map(int, fin.readline().split()))
		degrees = [0] * (n + 1)
		edges = []
		for i in range(m):
			(u, v) = map(int, fin.readline().split())
			degrees[u] += 1
			degrees[v] += 1
			edges.append((u, v))
		return cls(n, m, penalties, degrees, edges)

	def delete_one(self):
		min_penalty = 100000
		for (penalty, degree) in zip(self.penalties, self.degrees):
			if degree % 2 == 1:
				min_penalty = min(min_penalty, penalty)
		return min_penalty

	def delete_two(self):
		min_penalty = 100000
		for (u, v) in self.edges:
			if (self.degrees[u] + self.degrees[v]) % 2 == 0:
				min_penalty = min(min_penalty, self.penalties[u] + self.penalties[v])
		return min_penalty

	def solve(self):
		if self.m % 2 == 0:
			return 0
		return min(self.delete_one(), self.delete_two())

def main():
	if '--local-run' in sys.argv:
		fin = open('input.txt', 'r')
		fout = open('output.txt', 'w')
	else:
		fin = sys.stdin
		fout = sys.stdout
	num = int(fin.readline())
	for i in range(num):
		print(Solver.read(fin).solve(), file=fout)
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	minn = 100000
	mina = 100000
	b = list((0 for i in range(n)))
	for i in range(m):
		(x, y) = map(int, input().split())
		if a[x - 1] + a[y - 1] < mina:
			mina = a[x - 1] + a[y - 1]
		b[x - 1] += 1
		b[y - 1] += 1
	if m % 2 == 0:
		print(0)
	else:
		for i in range(n):
			if b[i] % 2 == 1:
				if a[i] < minn:
					minn = a[i]
		r = min(mina, minn)
		if r == 100000:
			print(sum(a))
		else:
			print(r)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(*a,) = map(int, input().split())
	c = []
	nc = [0] * n
	for _ in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		c += [(x, y)]
		nc[x] += 1
		nc[y] += 1
	if m & 1:
		o = []
		for i in range(n):
			if nc[i] & 1:
				o += [a[i]]
		for (x, y) in c:
			if nc[x] & 1 | nc[y] & 1 == 0:
				o += [a[x] + a[y]]
	else:
		o = [0]
	print(min(o))


import sys
import math
from collections import defaultdict, Counter
from itertools import permutations
from collections import deque
from decimal import Decimal
from fractions import Fraction
from heapq import heappush, heappop
import bisect

def sin():
	return int(sys.stdin.readline())

def array():
	return list(map(int, sys.stdin.readline().strip().split()))

def two():
	return map(int, sys.stdin.readline().strip().split())

def multiple():
	return [int(x) for x in sys.stdin.readline().split()]

def string():
	return sys.stdin.readline().strip()

def sqrt(x):
	(low, high) = (0, x)
	while low <= high:
		mid = (low + high) // 2
		if mid * mid <= x < (mid + 1) * (mid + 1):
			return mid
		elif x < mid * mid:
			high = mid - 1
		else:
			low = mid + 1
t = sin()
for _ in range(t):
	(n, m) = multiple()
	arr = array()
	freq = [0] * (n + 1)
	pairs = []
	for _ in range(m):
		(a, b) = multiple()
		pairs.append((a, b))
		freq[a] += 1
		freq[b] += 1
	if m % 2:
		ans = sys.maxsize
		for i in range(1, n + 1):
			if freq[i] % 2:
				ans = min(ans, arr[i - 1])
		for (x, y) in pairs:
			if freq[x] % 2 == 0 and freq[y] % 2 == 0:
				ans = min(ans, arr[x - 1] + arr[y - 1])
		print(ans)
	else:
		print(0)


R = lambda : [*map(int, input().split())]
for _ in [0] * R()[0]:
	(n, m) = R()
	a = (0, *R())
	b = [R() for _ in [0] * m]
	c = [0] + [0] * n
	for (x, y) in b:
		c[x] += 1
		c[y] += 1
	print(m % 2 and min([x for (x, y) in zip(a, c) if y % 2] + [a[x] + a[y] for (x, y) in b if c[x] | c[y] & 1 ^ 1]))


def solve():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	pair = []
	frnd = {}
	for _ in range(m):
		(a, b) = map(int, input().split())
		pair.append((a, b))
		if a in frnd:
			frnd[a] += 1
		else:
			frnd[a] = 1
		if b in frnd:
			frnd[b] += 1
		else:
			frnd[b] = 1
	res = float('inf')
	if m % 2:
		for i in frnd:
			if frnd[i] % 2 == 1:
				res = min(res, arr[i - 1])
		for i in pair:
			(a, b) = i
			if frnd[a] % 2 == 0 and frnd[b] % 2 == 0:
				res = min(res, arr[a - 1] + arr[b - 1])
	else:
		res = 0
	return res
t = int(input())
while t:
	print(solve())
	t -= 1


import sys
input = sys.stdin.readline
t = int(input())
import collections
while t:
	t -= 1
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	deg = [0] * n
	l = []
	for i in range(m):
		(x, y) = map(int, input().split())
		l.append([x, y])
		deg[x - 1] += 1
		deg[y - 1] += 1
	a1 = 1000000009
	for i in range(n):
		if deg[i] % 2 != 0:
			a1 = min(a1, a[i])
	for i in range(m):
		if deg[l[i][0] - 1] % 2 == 0 and deg[l[i][1] - 1] % 2 == 0:
			a1 = min(a1, a[l[i][0] - 1] + a[l[i][1] - 1])
	if m % 2 == 0:
		print(0)
	else:
		print(a1)


for i in range(int(input())):
	(friends, pairs) = map(int, input().split())
	sad_list = list(map(int, input().split()))
	tract_list = [0] * friends
	pair_value_list = []
	array = []
	for i in range(pairs):
		(x, y) = map(int, input().split())
		pair_value_list.append(sad_list[x - 1] + sad_list[y - 1])
		tract_list[x - 1] += 1
		tract_list[y - 1] += 1
	if pairs % 2 != 0:
		for i in range(friends):
			if tract_list[i] % 2 != 0:
				array.append(sad_list[i])
		sorted_array = sorted(array)
		sorted_pair_value_list = sorted(pair_value_list)
		if len(array) > 0:
			print(min(sorted_array[0], sorted_pair_value_list[0]))
		else:
			print(sorted_pair_value_list[0])
	else:
		print(0)


def resi():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	brParova = [0] * n
	l = []
	for i in range(m):
		(x, y) = map(int, input().split())
		brParova[x - 1] += 1
		brParova[y - 1] += 1
		l.append([x - 1, y - 1])
	if m % 2 == 0:
		print(0)
		return
	min1 = 20001
	for i in range(n):
		if brParova[i] % 2 == 1 and min1 > a[i]:
			min1 = a[i]
	min2 = 20001
	for tmp in l:
		if brParova[tmp[0]] % 2 == 0 and brParova[tmp[1]] % 2 == 0 and (a[tmp[0]] + a[tmp[1]] < min2):
			min2 = a[tmp[0]] + a[tmp[1]]
	print(min(min1, min2))
for _ in range(int(input())):
	resi()


import sys
from collections import defaultdict as dd
inp = sys.stdin.readline
for _ in range(int(inp())):
	(n, m) = map(int, inp().split())
	a = list(map(int, inp().split()))
	fre = dd(list)
	ans = 100000
	for __ in range(m):
		(x, y) = map(int, inp().split())
		fre[x].append(y)
		fre[y].append(x)
		ans = min(ans, a[x - 1] + a[y - 1])
	if m % 2 == 0:
		print(0)
		continue
	for i in range(1, n + 1):
		if len(fre[i]) % 2 == 1:
			ans = min(ans, a[i - 1])
	print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict as dd
t = int(input())
while t:
	t -= 1
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	ct = [0] * (n + 1)
	l1 = []
	for x in range(1, m + 1):
		(a, b) = list(map(int, input().split()))
		l1.append([a, b])
		ct[a] += 1
		ct[b] += 1
	ans = 1000000001
	if m % 2 == 0:
		ans = 0
	else:
		for x in range(1, n + 1):
			if ct[x] % 2 == 1:
				ans = min(ans, l[x - 1])
		for x in range(1, m + 1):
			if ct[l1[x - 1][0]] % 2 == 0 and ct[l1[x - 1][1]] % 2 == 0:
				ans = min(ans, l[l1[x - 1][0] - 1] + l[l1[x - 1][1] - 1])
	sys.stdout.write(str(ans) + '\n')


case = int(input())
for i in range(case):
	(n, m) = (int(v) for v in input().split())
	uh = [int(v) for v in input().split()]
	uhp = 200000
	list1 = [0] * n
	for pair in range(m):
		(a, b) = (int(v) for v in input().split())
		list1[a - 1] += 1
		list1[b - 1] += 1
		if uh[a - 1] + uh[b - 1] < uhp:
			uhp = uh[a - 1] + uh[b - 1]
	if m % 2 == 0:
		print(0)
	else:
		evenl = 200000
		evens = 100000
		odd = 100000
		for k in range(n):
			if list1[k] % 2 == 1:
				if uh[k] < odd:
					odd = uh[k]
			else:
				pass
		print(min(odd, uhp))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	unhappiness = list(map(int, input().split()))
	deg = [0 for i in range(n + 1)]
	vts = []
	for i in range(m):
		(u, v) = map(int, input().split())
		deg[u] += 1
		deg[v] += 1
		vts.append((u, v))
	if m % 2 == 0:
		print(0)
	else:
		ans = 10 ** 20
		for i in range(1, n + 1):
			if deg[i] % 2 == 1:
				ans = min(ans, unhappiness[i - 1])
		for (u, v) in vts:
			if deg[u] % 2 == 0 and deg[v] % 2 == 0:
				ans = min(ans, unhappiness[u - 1] + unhappiness[v - 1])
		print(ans)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	S = []
	C = [0 for i in range(n + 1)]
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		S.append(A[x - 1] + A[y - 1])
		C[x] += 1
		C[y] += 1
	if m % 2 == 0:
		print(0)
	else:
		L = []
		for i in range(1, n + 1):
			if C[i] % 2:
				L.append(A[i - 1])
		L.sort()
		S.sort()
		if L:
			print(min(L[0], S[0]))
		else:
			print(S[0])


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	u = list(map(int, input().split()))
	if m % 2 == 0:
		for q in range(m):
			input()
		print(0)
	elif m == 1:
		(x, y) = map(int, input().split())
		print(min(u[x - 1], u[y - 1]))
	else:
		vertice = [0] * n
		ans = 100000.0
		for q in range(m):
			(a, b) = map(int, input().split())
			vertice[a - 1] += 1
			vertice[b - 1] += 1
			ans = min(u[a - 1] + u[b - 1], ans)
		other = 100000.0
		for i in range(n):
			if vertice[i] % 2 == 1:
				other = min(other, u[i])
			else:
				continue
		print(min(other, ans))


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(s) for s in input().split()]
	d = [0] * n
	w2 = sum(a)
	for i in range(m):
		(x, y) = map(int, input().split())
		d[x - 1] += 1
		d[y - 1] += 1
		w2 = min(w2, a[x - 1] + a[y - 1])
	w1 = sum(a)
	for i in range(n):
		if d[i] % 2 == 1:
			w1 = min(w1, a[i])
	if m % 2 == 1:
		print(min(w1, w2))
	else:
		print(0)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	mt = []
	C = [0 for i in range(n + 1)]
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		mt.append(lst[x - 1] + lst[y - 1])
		C[x] += 1
		C[y] += 1
	if m % 2 != 0:
		arr = []
		for i in range(1, n + 1):
			if C[i] % 2:
				arr.append(lst[i - 1])
		z = sorted(arr)
		mpt = sorted(mt)
		if len(arr) > 0:
			print(min(z[0], mpt[0]))
		else:
			print(mpt[0])
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	mp = {}
	ans = pow(2, 31) - 1
	for i in range(m):
		(a, b) = [int(x) for x in input().split()]
		if a in mp:
			mp[a] += 1
		else:
			mp[a] = 1
		if b in mp:
			mp[b] += 1
		else:
			mp[b] = 1
		ans = min(ans, arr[a - 1] + arr[b - 1])
	if m % 2 == 0:
		print(0)
	else:
		for i in range(1, n + 1):
			if i in mp and mp[i] % 2 == 1:
				ans = min(ans, arr[i - 1])
		print(ans)


def main():
	t = int(input())
	while t:
		t -= 1
		(n, m) = list(map(int, input().split()))
		deg = [0 for _ in range(n + 1)]
		x = []
		y = []
		sad = list(map(int, input().split()))
		for i in range(m):
			(a, b) = list(map(int, input().split()))
			x.append(a)
			y.append(b)
			deg[x[-1]] += 1
			deg[y[-1]] += 1
		if m % 2 == 0:
			print('0')
		else:
			min_v = sum(sad)
			for i in range(n):
				if deg[i + 1] % 2 == 1:
					min_v = min(sad[i], min_v)
			for i in range(m):
				if deg[x[i]] % 2 == 0 and deg[y[i]] % 2 == 0:
					min_v = min(sad[x[i] - 1] + sad[y[i] - 1], min_v)
			print(min_v)
main()


import math
from collections import defaultdict

def resolve(n, unhappiness_array, friend_pair):
	pair_num = len(friend_pair)
	if pair_num % 2 == 0:
		return 0
	in_weight = defaultdict(int)
	for item in friend_pair:
		in_weight[item[0]] += 1
		in_weight[item[1]] += 1
	temp_palnty = float('inf')
	for (index, value) in enumerate(unhappiness_array):
		if in_weight[index + 1] % 2 == 1 and value < temp_palnty:
			temp_palnty = value
	for item in friend_pair:
		temp_2 = unhappiness_array[item[0] - 1] + unhappiness_array[item[1] - 1]
		if in_weight[item[0]] % 2 == 0 and in_weight[item[1]] % 2 == 0 and (temp_2 < temp_palnty):
			temp_palnty = temp_2
	return temp_palnty

def read_input():
	ints = input().split(' ')
	n = int(ints[0])
	m = int(ints[1])
	unhappiness_array = []
	second_line = input().split(' ')
	for item in second_line:
		unhappiness_array.append(int(item))
	friend_pair = []
	for index in range(m):
		next_line = input().split(' ')
		friend_pair.append((int(next_line[0]), int(next_line[1])))
	return (n, unhappiness_array, friend_pair)
case_num = int(input())
if not case_num == 0:
	for index in range(case_num):
		(n, unhappiness_array, friend_pair) = read_input()
		res = resolve(n, unhappiness_array, friend_pair)
		print(res)


from cmath import inf
for q in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	deg = [0 for i in range(n + 1)]
	lis = []
	for i in range(m):
		(x, y) = [int(x) for x in input().split()]
		lis.append([x, y])
		deg[x] += 1
		deg[y] += 1
	if m % 2 == 0:
		print(0)
		continue
	ans = inf
	(e1, e2) = (inf, inf)
	for i in range(1, n + 1):
		if deg[i] % 2:
			ans = min(ans, arr[i - 1])
	for (x, y) in lis:
		if deg[x] % 2 == 0 and deg[y] % 2 == 0:
			ans = min(ans, arr[x - 1] + arr[y - 1])
	print(ans)


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
t = num_inp()
for _ in range(t):
	(n, m) = sp_inp()
	l = arr_inp()
	pair = []
	count = [0 for _ in range(n)]
	for i in range(m):
		(x, y) = sp_inp()
		pair.append((x, y))
		count[x - 1] += 1
		count[y - 1] += 1
	if m % 2 == 0:
		print(0)
	else:
		ans = 2 * max(l)
		for i in range(n):
			if count[i] % 2 != 0:
				ans = min(ans, l[i])
		for i in pair:
			if count[i[0] - 1] % 2 == 0 and count[i[1] - 1] % 2 == 0:
				ans = min(ans, l[i[0] - 1] + l[i[1] - 1])
		print(ans)


t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	if m % 2 == 0:
		input()
		for mm in range(m):
			input()
		print(0)
	else:
		a = list(map(int, input().split()))
		b = [0 for nn in range(n)]
		mat = []
		lofxy = []
		for mm in range(m):
			(x, y) = map(int, input().split())
			lofxy.append((x, y))
			b[x - 1] += 1
			b[y - 1] += 1
		ini = True
		found = False
		min0 = None
		for nn in range(n):
			if b[nn] % 2 != 0:
				if ini:
					min0 = a[nn]
					ini = False
				else:
					min0 = min(min0, a[nn])
				found = True
		minp = None
		ini = True
		for e in lofxy:
			if ini and b[e[0] - 1] % 2 == 0 and (b[e[1] - 1] % 2 == 0):
				minp = a[e[0] - 1] + a[e[1] - 1]
				ini = False
			elif b[e[0] - 1] % 2 == 0 and b[e[1] - 1] % 2 == 0:
				minp = min(minp, a[e[0] - 1] + a[e[1] - 1])
		if min0 == None:
			print(minp)
		elif minp == None:
			print(min0)
		else:
			print(min(min0, minp))


import math

def party(unhapp, friends, counter):
	n = len(unhapp)
	best = math.inf
	for i in range(n):
		if counter[i] % 2 == 1:
			best = min(best, unhapp[i])
	for (v, k) in friends:
		if counter[v] % 2 == 0 and counter[k] % 2 == 0:
			best = min(best, unhapp[v] + unhapp[k])
	return best
tests = int(input())
for _ in range(tests):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	edges = []
	counter = [0 for _ in range(n)]
	for _ in range(m):
		(v, k) = [int(x) - 1 for x in input().split()]
		counter[v] += 1
		counter[k] += 1
		edges.append((v, k))
	print(party(a, edges, counter) if m % 2 == 1 else 0)


from collections import Counter, defaultdict
from bisect import bisect_left
import math
n = int(input())
ans = []
for _ in range(n):
	res = float('inf')
	(m, k) = map(int, input().split())
	mem = list(map(int, input().split()))
	graph = [[] for _ in range(m)]
	for _ in range(k):
		(i, j) = map(int, input().split())
		i -= 1
		j -= 1
		graph[i].append(j)
		graph[j].append(i)
		res = min(res, mem[i] + mem[j])
	if k % 2 == 0:
		ans.append(0)
	else:
		for i in range(m):
			if len(graph[i]) % 2:
				res = min(res, mem[i])
		ans.append(res)
for a in ans:
	print(a)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = [0] * (n + 1)
	l2 = []
	ans = 10 ** 4 * 2 + 1
	for i in range(m):
		(x, y) = map(int, input().split())
		l1[x] += 1
		l1[y] += 1
		l2.append((x, y))
	if m % 2 == 0:
		print(0)
	else:
		for (j, i) in enumerate(l1):
			if i % 2 == 1:
				ans = min(ans, l[j - 1])
		for i in l2:
			if l1[i[0]] % 2 == 0 and l1[i[1]] % 2 == 0:
				ans = min(ans, l[i[0] - 1] + l[i[1] - 1])
		print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	x = [0] * m
	y = [0] * m
	deg = [0] * n
	for i in range(m):
		(x[i], y[i]) = map(lambda x: int(x) - 1, input().split())
		deg[x[i]] += 1
		deg[y[i]] += 1
	if m % 2 == 0:
		print(0)
		continue
	ans = 1000000000
	for i in range(n):
		if deg[i] % 2 == 1:
			ans = min(ans, a[i])
	for i in range(m):
		if deg[x[i]] % 2 == 0 and deg[y[i]] % 2 == 0:
			ans = min(ans, a[x[i]] + a[y[i]])
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	unhappiness = list(map(int, input().split(' ')))
	degree = [0] * n
	pairs = []
	for i in range(m):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		degree[a] += 1
		degree[b] += 1
		pairs.append((a, b))
	if not m % 2:
		print(0)
	else:
		ans = float('inf')
		for i in range(n):
			if degree[i] % 2:
				ans = min(ans, unhappiness[i])
		for (a, b) in pairs:
			if not degree[a] % 2 and (not degree[b] % 2):
				ans = min(ans, unhappiness[a] + unhappiness[b])
		print(ans)


test = int(input())
while test:
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ind = [0] * n
	arr1 = [0] * m
	arr2 = [0] * m
	for i in range(m):
		(x, y) = map(int, input().split())
		(arr1[i], arr2[i]) = (x, y)
		ind[arr1[i] - 1] += 1
		ind[arr2[i] - 1] += 1
	if not m % 2:
		print(0)
	else:
		ans = float('inf')
		for i in range(n):
			if ind[i] % 2:
				ans = min(ans, a[i])
		for i in range(m):
			if ind[arr1[i] - 1] % 2 == 0 and ind[arr2[i] - 1] % 2 == 0:
				ans = min(ans, a[arr1[i] - 1] + a[arr2[i] - 1])
		print(ans)
	test -= 1


def solve():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = {}
	cnt = [0 for i in range(n)]
	s = sum(arr)
	for i in range(m):
		(a, b) = map(int, input().split())
		cnt[a - 1] += 1
		cnt[b - 1] += 1
		d[a, b] = 1
	if m % 2 == 0:
		print(0)
		return
	ans = s
	for x in d:
		i = x[0]
		j = x[1]
		temp = cnt[i - 1] + cnt[j - 1]
		if (i, j) in d:
			temp -= 1
		if (m - temp) % 2 == 0:
			ans = min(ans, arr[i - 1] + arr[j - 1])
	for i in range(n):
		if (m - cnt[i - 1]) % 2 == 0:
			ans = min(ans, arr[i - 1])
	print(ans)
	return
for i in range(int(input())):
	solve()


for i in range(int(input())):
	(num_guest, num_pair) = input().split(' ')
	happiness = [int(x) for x in input().split(' ')]
	temp_list = happiness.copy()
	temp_list.sort()
	friends = []
	weight = [0] * int(num_guest)
	for j in range(int(num_pair)):
		friend = [int(x) for x in input().split(' ')]
		friends.append(friend)
		weight[friend[0] - 1] += 1
		weight[friend[1] - 1] += 1
	if int(num_pair) % 2 == 0:
		print(0)
	else:
		min_happiness_1 = 1000000000
		min_happiness_2 = 1000000000
		int2 = 0
		while int2 < len(happiness):
			if weight[int2] % 2 != 0 and happiness[int2] < min_happiness_1:
				min_happiness_1 = happiness[int2]
			int2 += 1
		for elems in friends:
			if weight[elems[0] - 1] % 2 == 0 and weight[elems[1] - 1] % 2 == 0 and (happiness[elems[0] - 1] + happiness[elems[1] - 1] < min_happiness_2):
				min_happiness_2 = happiness[elems[0] - 1] + happiness[elems[1] - 1]
		print(min(min_happiness_1, min_happiness_2))


from collections import Counter
for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = [*map(int, input().split())]
	tm = []
	r = []
	cost = []
	for i in range(m):
		(a, b) = map(int, input().split())
		tm.extend([a - 1, b - 1])
		r.append((a - 1, b - 1))
	if m % 2:
		tm = Counter(tm)
		for i in r:
			if tm[i[0]] % 2 == 1:
				cost.append(l[i[0]])
			if tm[i[1]] % 2 == 1:
				cost.append(l[i[1]])
			if tm[i[0]] % 2 == 0 and tm[i[1]] % 2 == 0:
				cost.append(l[i[0]] + l[i[1]])
		print(min(cost))
	else:
		print(0)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	lis = list(map(int, input().split()))
	arr = []
	adj = [[] for i in range(n + 1)]
	cadj = [0 for i in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
		cadj[a - 1] += 1
		cadj[b - 1] += 1
		arr.append(sum([lis[a - 1], lis[b - 1]]))
	for i in range(len(cadj)):
		if cadj[i] % 2 == 1:
			arr.append(lis[i])
	if m % 2:
		print(min(arr))
	else:
		print(0)


from collections import defaultdict

def solve(A, B):
	if len(B) % 2 == 0:
		return 0
	count = defaultdict(int)
	for pair in B:
		count[pair[0]] += 1
		count[pair[1]] += 1
	idx = -1
	minV = float('inf')
	for (i, v) in enumerate(A):
		id = i + 1
		if count[id] % 2 == 1 and v < minV:
			minV = v
			idx = i
	for pair in B:
		v = A[pair[0] - 1] + A[pair[1] - 1]
		if count[pair[0]] % 2 == 0 and count[pair[1]] % 2 == 0 and (v < minV):
			minV = v
	return minV

def readB(m):
	ans = []
	for _ in range(m):
		s = input().split(' ')
		ans.append([int(s[0]), int(s[1])])
	return ans

def readA():
	s = input()
	return [int(x) for x in s.split(' ')]

def main():
	n = int(input())
	for _ in range(n):
		s = input().split(' ')
		a = int(s[0])
		b = int(s[1])
		A = readA()
		B = readB(b)
		print(solve(A, B))
		pass
	pass
main()


t = int(input())
while t > 0:
	t -= 1
	(n, m) = [int(x) for x in input().split(' ')]
	weights = [int(x) for x in input().split(' ')]
	degree = dict()
	edges = []
	for i in range(m):
		(a, b) = [int(x) for x in input().split(' ')]
		edges.append([a, b])
		degree[a] = degree.get(a, 0) + 1
		degree[b] = degree.get(b, 0) + 1
	if m % 2 == 0:
		print(0)
		continue
	odd_degree = [weights[x - 1] for x in range(1, n + 1) if degree.get(x, 0) % 2 == 1]
	if odd_degree:
		odd_degree_min = min(odd_degree)
	else:
		odd_degree_min = float('inf')
	pair_min = min([weights[x - 1] + weights[y - 1] for (x, y) in edges])
	print(min(pair_min, odd_degree_min))


import math
from collections import Counter
from collections import defaultdict
import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def solve(ques, arr, s):
	if len(ques) % 2 == 0:
		return 0
	dd = Counter(s)
	d = {}
	for i in range(len(arr)):
		d[i + 1] = arr[i]
	minn = float('inf')
	for (n1, n2) in ques:
		if dd[n1] % 2 != 0:
			minn = min(minn, d[n1])
		if dd[n2] % 2 != 0:
			minn = min(minn, d[n2])
	for (n1, n2) in ques:
		if dd[n1] % 2 == 0 and dd[n2] % 2 == 0:
			minn = min(minn, d[n1] + d[n2])
	return minn
t = int(input())
for _ in range(t):
	(n, m) = get_ints()
	arr = get_ints()
	ques = []
	s = []
	for i in range(m):
		(a, b) = get_ints()
		s.append(a)
		s.append(b)
		ques.append((a, b))
	print(solve(ques, arr, s))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	seq = tuple((int(i) for i in input().split()))
	ind_friends = {}
	friends = set()
	cnt_odd = 10 ** 5
	for _ in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		friends.add((x, y))
		ind_friends[x] = ind_friends.get(x, 0) + 1
		ind_friends[y] = ind_friends.get(y, 0) + 1
	if m % 2:
		for i in ind_friends:
			if ind_friends[i] % 2:
				if seq[i] < cnt_odd:
					cnt_odd = seq[i]
		for i in sorted(friends, key=lambda x: seq[x[0]] + seq[x[1]]):
			if seq[i[0]] + seq[i[1]] > cnt_odd:
				print(cnt_odd)
				break
			elif (ind_friends[i[0]] + ind_friends[i[1]]) % 2 == 0:
				if ind_friends[i[0]] % 2:
					print(seq[i[0]])
					break
				elif ind_friends[i[1]] % 2:
					print(seq[i[1]])
					break
				else:
					print(seq[i[0]] + seq[i[1]])
					break
		else:
			print(sum(seq))
	else:
		print(0)


from collections import defaultdict
T = int(input())
while T:
	T -= 1
	(n, m) = map(int, input().split())
	unhappy = list(map(int, input().split()))
	dic = defaultdict(list)
	if m % 2 == 0:
		for _ in range(m):
			(a, b) = map(int, input().split())
		print(0)
		continue
	arr = float('inf')
	dic = defaultdict(int)
	for _ in range(m):
		(a, b) = map(int, input().split())
		dic[a - 1] += 1
		dic[b - 1] += 1
		x = unhappy[a - 1] + unhappy[b - 1]
		arr = min(x, arr)
	for i in range(0, n):
		if dic[i] % 2 == 1:
			arr = min(arr, unhappy[i])
	print(arr)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	friends = []
	degrees = defaultdict(int)
	for i in range(m):
		(x, y) = map(int, input().split())
		friends.append((x, y))
		degrees[x] += 1
		degrees[y] += 1
	ans = 10 ** 5
	if len(friends) % 2 == 0:
		print(0)
	else:
		for (x, y) in friends:
			if degrees[x] % 2 == 1:
				ans = min(ans, a[x - 1])
			if degrees[y] % 2 == 1:
				ans = min(ans, a[y - 1])
			if degrees[x] % 2 == 0 and degrees[y] % 2 == 0:
				ans = min(ans, a[x - 1] + a[y - 1])
		print(ans)


t = int(input())
for j in range(t):
	inn = input().split(' ')
	(n, m) = (int(inn[0]), int(inn[1]))
	(deg, pairs) = ([0] * (n + 1), [])
	a = [int(x) for x in input().split(' ')]
	a.insert(0, 0)
	for i in range(m):
		inn = input().split(' ')
		(x, y) = (int(inn[0]), int(inn[1]))
		deg[x] += 1
		deg[y] += 1
		pairs.append([x, y])
	if m % 2 == 0:
		print(0)
		continue
	result = 1 * 10 ** 10
	for pair in pairs:
		if deg[pair[0]] % 2 == 1:
			result = min(result, a[pair[0]])
		if deg[pair[1]] % 2 == 1:
			result = min(result, a[pair[1]])
		if deg[pair[0]] % 2 == 0 and deg[pair[1]] % 2 == 0:
			result = min(result, a[pair[0]] + a[pair[1]])
	print(result)
	t -= 1


from math import inf

def solve(n, a, friendships):
	adj = [[] for _ in range(n)]
	for (src, dest) in friendships:
		adj[src - 1].append(dest - 1)
		adj[dest - 1].append(src - 1)
	if len(friendships) % 2 == 0:
		return 0
	minimum_unhappiness = inf
	for person in range(n):
		if len(adj[person]) % 2 == 1:
			minimum_unhappiness = min(minimum_unhappiness, a[person])
	for (src, dst) in friendships:
		if len(adj[src - 1]) % 2 == 0 and len(adj[dst - 1]) % 2 == 0:
			minimum_unhappiness = min(minimum_unhappiness, a[src - 1] + a[dst - 1])
	return minimum_unhappiness
t = int(input())
for _ in range(t):
	(n, m) = [int(component) for component in input().split(' ')]
	a = [int(component) for component in input().split(' ')]
	friendships = []
	for row in range(m):
		friendships.append([int(component) for component in input().split(' ')])
	print(solve(n, a, friendships))


ans = ''
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	res = float('inf')
	degree = [0] * n
	edges = []
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		edges.append([x - 1, y - 1])
		degree[x - 1] += 1
		degree[y - 1] += 1
	if m % 2 == 0 or n == 1:
		ans += '0\n'
		continue
	for i in range(n):
		if degree[i] % 2 == 1:
			res = min(res, arr[i])
	for (i, j) in edges:
		if degree[i] % 2 == 0 and degree[j] % 2 == 0:
			res = min(res, arr[i] + arr[j])
	ans += str(res) + '\n'
print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	mn = float('inf')
	lst = []
	for q in range(m):
		(l, r) = map(int, input().split())
		mn = min(a[l - 1] + a[r - 1], mn)
		lst.append(l)
		lst.append(r)
	d = Counter(lst)
	if m % 2 == 0:
		print(0)
	else:
		for j in d:
			if d[j] % 2 == 1:
				mn = min(a[j - 1], mn)
		print(mn)


import collections
x = int(input())
for jj in range(x):
	(n, m) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	if m == 0:
		print(0)
		continue
	dic = {}
	for i in range(m):
		(x, y) = [int(ii) for ii in input().split(' ')]
		if x not in dic:
			dic[x] = [y]
		else:
			dic[x].append(y)
		if y not in dic:
			dic[y] = [x]
		else:
			dic[y].append(x)
	if m % 2 == 0:
		print(0)
		continue
	p = sorted(dic.keys(), key=lambda o: arr[o - 1])
	ans = sum(arr)
	tk = -1
	for i in range(len(p)):
		if len(dic[p[i]]) % 2 == 1:
			tk = i
			ans = arr[p[i] - 1]
			break
	if ans == 0:
		print(0)
		continue
	if 0 <= tk < 2:
		print(ans)
		continue
	else:
		for i in range(len(p)):
			if arr[p[i] - 1] <= ans // 2:
				dic[p[i]].sort(key=lambda o: arr[o - 1])
				ans = min(ans, arr[p[i] - 1] + arr[dic[p[i]][0] - 1])
			else:
				break
		print(ans)
		continue


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	frs = [0] * n
	minf = [10 ** 5] * n
	for _ in range(m):
		(a, b) = map(int, input().split())
		frs[a - 1] += 1
		frs[b - 1] += 1
		minf[a - 1] = min(minf[a - 1], arr[b - 1])
		minf[b - 1] = min(minf[b - 1], arr[a - 1])
	if m % 2 == 0:
		print(0)
	else:
		mn = 10 ** 5
		for i in range(n):
			if frs[i] % 2 and arr[i] < mn:
				mn = arr[i]
		for i in range(n):
			if frs[i] and arr[i] + minf[i] < mn:
				mn = arr[i] + minf[i]
		print(mn)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	freq = {}
	edges = []
	for _ in range(m):
		(n1, n2) = map(int, input().split())
		edges.append([n1, n2])
		if n1 not in freq:
			freq[n1] = 0
		if n2 not in freq:
			freq[n2] = 0
		freq[n1] = freq[n1] + 1
		freq[n2] = freq[n2] + 1
	odds = []
	for i in freq:
		if freq[i] % 2 == 1:
			odds.append(i)
	if m % 2 == 0:
		print(0)
	else:
		ans = float('inf')
		for i in odds:
			ans = min(ans, a[i - 1])
		for (n1, n2) in edges:
			if freq[n1] % 2 == 0 and freq[n2] % 2 == 0:
				ans = min(ans, a[n1 - 1] + a[n2 - 1])
		print(ans)
	t = t - 1


from collections import Counter, defaultdict
import math

def solve():
	(n, m) = list(map(int, input().split()))
	vis = [False] * n
	unh = list(map(int, input().split()))
	graph = defaultdict(list)
	for _ in range(m):
		(u, v) = list(map(int, input().split()))
		graph[u].append(v)
		graph[v].append(u)
	if m % 2 == 0:
		print(0)
		return
	odd = math.inf
	even = set()
	for i in graph:
		if len(graph[i]) % 2:
			odd = min(odd, unh[i - 1])
		else:
			even.add(i)
	ev = math.inf
	for i in even:
		for j in graph[i]:
			if j in even:
				ev = min(ev, unh[i - 1] + unh[j - 1])
	print(min(ev, odd))
for _ in range(int(input())):
	solve()


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	g = [[] for _ in range(n)]
	for _ in range(m):
		(x, y) = (int(x) - 1 for x in input().split())
		g[x].append(y)
		g[y].append(x)
	if m % 2 == 0:
		print(0)
		continue
	opt = math.inf
	for (i, x) in enumerate(a):
		if len(g[i]) % 2 == 1:
			opt = min(opt, x)
		else:
			for j in g[i]:
				opt = min(opt, x + a[j])
	print(opt)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	friends = defaultdict(list)
	ans = 100000000
	for _ in range(m):
		(x, y) = map(int, input().split())
		friends[x].append(y)
		friends[y].append(x)
		ans = min(ans, arr[x - 1] + arr[y - 1])
	if m % 2 == 0:
		print(0)
		continue
	for i in range(1, n + 1):
		if len(friends[i]) % 2 != 0:
			ans = min(ans, arr[i - 1])
	print(ans)


def minUnhappiness(n, m, unhaparr, friends):
	friends = list(set((tuple(sorted(fr)) for fr in friends)))
	numfriends = [0] * n
	for (x, y) in friends:
		numfriends[x - 1] += 1
		numfriends[y - 1] += 1
	unhappiness_idxs = sorted(list(range(n)), key=lambda x: unhaparr[x])
	if m % 2 == 0:
		ans = 0
	else:
		ans = float('inf')
		for idx in unhappiness_idxs:
			if numfriends[idx] % 2:
				ans = unhaparr[idx]
				break
		for (x, y) in friends:
			if (numfriends[x - 1] + numfriends[y - 1] + 1) % 2:
				ans = min(ans, unhaparr[x - 1] + unhaparr[y - 1])
	return ans

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		unhaparr = list(map(int, input().split()))
		friends = []
		for k in range(m):
			friends.append(list(map(int, input().split())))
		print(minUnhappiness(n, m, unhaparr, friends))
main()


def check(a, b):
	dinh = str(a) + ' ' + str(b)
	if dinh in ke_nhau:
		return True
	else:
		return False
for _ in range(int(input())):
	s = input()
	tmp = s.split()
	n = int(tmp[0])
	m = int(tmp[1])
	s = input()
	tmp = s.split()
	a = [0]
	for i in tmp:
		a += [int(i)]
	bac = [0] * (n + 1)
	(x, y) = ([0], [0])
	for _ in range(m):
		s = input()
		tmp = s.split()
		bac[int(tmp[0])] += 1
		bac[int(tmp[1])] += 1
		x += [int(tmp[0])]
		y += [int(tmp[1])]
	if m % 2 == 0:
		print(0)
	else:
		th1 = sum(a)
		th2 = sum(a)
		for i in range(1, n + 1):
			if bac[i] % 2 == 1 and (m - bac[i]) % 2 == 0:
				th1 = min(th1, a[i])
		for i in range(1, m + 1):
			if bac[x[i]] % 2 == 0 and bac[y[i]] % 2 == 0 or (bac[x[i]] % 2 == 1 and bac[y[i]] % 2 == 1):
				th2 = min(th2, a[x[i]] + a[y[i]])
		print(min(th1, th2))


def invite():
	(n, m) = [int(x) for x in input().split()]
	Fgraph = {}
	unhappy = [int(x) for x in input().split()]
	edges = []
	for i in range(m):
		(a, b) = [int(x) for x in input().split()]
		edges.append((a, b))
		if a in Fgraph:
			Fgraph[a] += [b]
		else:
			Fgraph[a] = [b]
		if b in Fgraph:
			Fgraph[b] += [a]
		else:
			Fgraph[b] = [a]
	if m % 2 == 0:
		return 0
	num_Edges = []
	for i in range(1, n + 1):
		if i in Fgraph:
			num_Edges.append(len(Fgraph[i]))
		else:
			num_Edges.append(0)
	ans1 = 9999999
	for i in range(n):
		if num_Edges[i] % 2 == 1:
			ans1 = min(ans1, unhappy[i])
	ans2 = 9999999
	for i in range(m):
		(a, b) = edges[i]
		ans2 = min(ans2, unhappy[a - 1] + unhappy[b - 1])
	return min(ans1, ans2)
for i in range(int(input())):
	print(invite())


from collections import *

def main():
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		a = list(map(int, input().split()))
		c = Counter()
		g = []
		for i in range(m):
			(x, y) = map(int, input().split())
			c[x] += 1
			c[y] += 1
			g.append([x, y])
		if m % 2 == 0:
			print(0)
			continue
		res = 0
		b = []
		for i in range(1, n + 1):
			if c[i] & 1:
				b.append(a[i - 1])
		res = 200000
		for i in range(m):
			if c[g[i][0]] % 2 == 0 and c[g[i][1]] % 2 == 0:
				res = min(res, a[g[i][0] - 1] + a[g[i][1] - 1])
		if len(b):
			res = min(res, sorted(b)[0])
		print(res)
main()


for p in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	(f, g, d) = ([], [], {})
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		f.append(x)
		g.append(y)
		if d.get(x):
			d[x] += 1
		else:
			d[x] = 1
		if d.get(y):
			d[y] += 1
		else:
			d[y] = 1
	if m % 2 == 0:
		print(0)
	else:
		(v, q) = (float('inf'), [])
		for i in d.keys():
			if d[i] % 2:
				q.append(a[i - 1])
		q.sort()
		if q:
			v = min(v, q[0])
		for i in range(len(f)):
			if d[f[i]] % 2 == 0 and d[g[i]] % 2 == 0:
				v = min(v, a[f[i] - 1] + a[g[i] - 1])
		print(v)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(j) for j in input().split()]
	f = [0] * n
	g = [[] for j in range(n)]
	for j in range(m):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		f[x] += 1
		f[y] += 1
		g[x] += [y]
		g[y] += [x]
	if m % 2:
		q = 9 ** 9
		for j in range(n):
			if f[j] % 2:
				q = min(q, a[j])
			else:
				for t in g[j]:
					if f[t] % 2 < 1:
						q = min(q, a[t] + a[j])
		print(q)
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	As = input().split()
	As = [int(i) for i in As]
	edges = [[] for _ in range(n)]
	for __ in range(m):
		(a, b) = input().split()
		(a, b) = (int(a), int(b))
		edges[a - 1].append(b - 1)
		edges[b - 1].append(a - 1)
	if m % 2 == 0:
		print(0)
	else:
		As_with_idx = [[a, i] for (i, a) in enumerate(As)]
		As_with_idx.sort(key=lambda x: x[0])
		min_cost = 1000000
		selected_set = set()
		for (a, idx) in As_with_idx:
			if a > min_cost:
				break
			if len(edges[idx]) % 2 == 1:
				min_cost = min(min_cost, a)
				break
			else:
				for e in edges[idx]:
					if e in selected_set:
						min_cost = min(min_cost, As[e] + a)
			selected_set.add(idx)
		print(min_cost)


from collections import Counter, defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	d = defaultdict(int)
	pair = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		pair.append([x, y])
		d[x] += 1
		d[y] += 1
	if m % 2 == 0:
		print(0)
	else:
		ans = float('inf')
		for i in d:
			if d[i] % 2:
				ans = min(ans, a[i - 1])
		for (i, j) in pair:
			if d[i] % 2 == 0 and d[j] % 2 == 0:
				ans = min(ans, a[i - 1] + a[j - 1])
		print(ans)


from collections import Counter
t = int(input())
for x in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	f = []
	c = Counter()
	for _ in range(m):
		(u, v) = map(int, input().split())
		f.append((u, v))
		c[u] += 1
		c[v] += 1
	if m % 2 == 0:
		print(0)
		continue
	ans = float('inf')
	for i in c:
		if c[i] & 1:
			ans = min(ans, a[i - 1])
	for (u, v) in f:
		if a[u - 1] + a[v - 1] < ans:
			cakes = m - c[u] - c[v] + 1
			if cakes % 2 == 0:
				ans = a[u - 1] + a[v - 1]
	print(ans)


import math
t = int(input())
ans = []
for i in range(t):
	inp = list(map(int, input().split()))
	(n, m) = inp
	unhappiness = list(map(int, input().split()))
	friends = []
	for i in range(m):
		friends.append(list(map(int, input().split())))
	adj = [[] for i in range(n + 1)]
	for f in friends:
		adj[f[0]].append(f[1])
		adj[f[1]].append(f[0])
	if len(friends) % 2 == 0:
		ans.append(0)
		continue
	minunhp = math.inf
	for i in range(n):
		if len(adj[i + 1]) % 2 == 1:
			if unhappiness[i] < minunhp:
				minunhp = unhappiness[i]
	for f in friends:
		if len(adj[f[0]]) % 2 == 0 and len(adj[f[1]]) % 2 == 0:
			if unhappiness[f[0] - 1] + unhappiness[f[1] - 1] < minunhp:
				minunhp = unhappiness[f[0] - 1] + unhappiness[f[1] - 1]
	ans.append(minunhp)
for a in ans:
	print(a)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = [0 for _ in range(n + 1)]
	x = []
	y = []
	for _ in range(m):
		(r1, r2) = list(map(int, input().split()))
		d[r1] += 1
		d[r2] += 1
		x.append(r1)
		y.append(r2)
	ans = 10000000
	if m % 2 == 0:
		ans = 0
	for i in range(1, n + 1):
		if d[i] % 2 == 1:
			ans = min(ans, a[i - 1])
	for i in range(m):
		if d[x[i]] % 2 == 0 and d[y[i]] % 2 == 0:
			ans = min(ans, a[x[i] - 1] + a[y[i] - 1])
	print(ans)


from posixpath import split
t = int(input())
while t > 0:
	x = input().split()
	(n, m) = (int(x[0]), int(x[1]))
	a = input().split()
	b = []
	count = [0 for i in range(n)]
	for i in range(n):
		a[i] = int(a[i])
	for i in range(m):
		x = input().split()
		(c, d) = (int(x[0]), int(x[1]))
		count[c - 1] += 1
		count[d - 1] += 1
		b.append([c - 1, d - 1])
	if m % 2 == 0:
		print('0')
	else:
		ans = 10 ** 9 + 10
		for i in range(n):
			if count[i] % 2:
				ans = min(ans, a[i])
		for i in range(m):
			if count[b[i][0]] % 2 == 0 and count[b[i][1]] % 2 == 0:
				ans = min(ans, a[b[i][0]] + a[b[i][1]])
		print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	pairs = list()
	neighbours = [list() for i in range(n)]
	for i in range(m):
		(x, y) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		pairs.append((x, y))
		neighbours[x].append(y)
		neighbours[y].append(x)
	if m % 2 == 0:
		print(0)
		continue
	minUnhappinessWithOneUninvited = 1000000000.0
	for i in range(n):
		if len(neighbours[i]) % 2 == 1:
			minUnhappinessWithOneUninvited = min(minUnhappinessWithOneUninvited, a[i])
	minUnhappinessWithTwoUninvited = 1000000000.0
	for (member1, member2) in pairs:
		if (len(neighbours[member1]) + len(neighbours[member2])) % 2 == 0:
			minUnhappinessWithTwoUninvited = min(minUnhappinessWithTwoUninvited, a[member1] + a[member2])
	print(min(minUnhappinessWithOneUninvited, minUnhappinessWithTwoUninvited))


T = int(input())
for t in range(0, T):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	lst = []
	for i in range(0, m):
		(x, y) = map(int, input().split())
		lst.append([x, y])
	if m % 2 == 0:
		print(0)
	else:
		ans = 2 * 10000 + 1
		freq = {}
		for i in range(0, m):
			if lst[i][0] not in freq:
				freq[lst[i][0]] = 1
			else:
				freq[lst[i][0]] += 1
			if lst[i][1] not in freq:
				freq[lst[i][1]] = 1
			else:
				freq[lst[i][1]] += 1
		for item in lst:
			if (freq[item[0]] + freq[item[1]]) % 2 == 0:
				ans = min(ans, a[item[0] - 1] + a[item[1] - 1])
		for i in range(0, n):
			if i + 1 in freq:
				if freq[i + 1] % 2 != 0:
					ans = min(ans, a[i])
		print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	y = []
	d = {}
	ans = 100001
	for j in range(m):
		(a, b) = map(int, input().split())
		y.append([a, b])
	if m % 2 == 0:
		print(0)
	else:
		for j in range(m):
			if y[j][0] in d:
				d[y[j][0]] += 1
			elif y[j][0] not in d:
				d[y[j][0]] = 1
			if y[j][1] in d:
				d[y[j][1]] += 1
			elif y[j][1] not in d:
				d[y[j][1]] = 1
		for j in range(1, n + 1):
			if j not in d:
				continue
			if d[j] % 2 == 1:
				ans = min(ans, x[j - 1])
		for j in range(m):
			if d[y[j][0]] % 2 == 0 and d[y[j][1]] % 2 == 0:
				ans = min(ans, x[y[j][0] - 1] + x[y[j][1] - 1])
		print(ans)


from collections import defaultdict
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	count = m
	mini = float('inf')
	d = defaultdict(lambda : [])
	b = []
	for i in range(m):
		(x, y) = map(int, input().split())
		d[x].append(y)
		d[y].append(x)
		mini = min(mini, a[x - 1] + a[y - 1])
	if m % 2 == 0:
		print(0)
	else:
		for i in range(1, n + 1):
			if len(d[i]) % 2 == 1:
				mini = min(mini, a[i - 1])
		print(mini)
	t = t - 1


from typing import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	p = []
	d = []
	for i in range(m):
		(u, v) = map(int, input().split())
		p.append([u, v])
		d += [u, v]
	if m & 1:
		c = Counter(d)
		ans = sum(a)
		for x in c:
			if not m - c[x] & 1:
				ans = min(ans, a[x - 1])
		for x in p:
			rem = 2 * m - 2 * (c[x[0]] + c[x[1]] - 1)
			if rem % 2 == 0:
				ans = min(ans, a[x[0] - 1] + a[x[1] - 1])
		print(ans)
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	count = [0] * (n + 1)
	pairs = []
	for _ in range(m):
		(a, b) = list(map(int, input().split(' ')))
		count[a] += 1
		count[b] += 1
		pairs.append((a, b))
	min_cost = 10 ** 5 + 1
	if m % 2 == 0:
		print(0)
		continue
	else:
		for (a, b) in pairs:
			if count[a] % 2 != 0:
				min_cost = min(min_cost, arr[a - 1])
			if count[b] % 2 != 0:
				min_cost = min(min_cost, arr[b - 1])
			if (count[b] + count[a]) % 2 == 0:
				min_cost = min(min_cost, arr[a - 1] + arr[b - 1])
	print(min_cost)


import sys, io, os, math
from math import ceil, log, gcd, sqrt
from itertools import permutations
from collections import defaultdict
import operator
mod = 1000000007
mod2 = 998244353
intinp = lambda : int(sys.stdin.readline())
strinp = lambda : sys.stdin.readline()
arrinp = lambda : list(map(int, sys.stdin.readline().strip().split()))
mulinp = lambda : map(int, sys.stdin.readline().strip().split())
power_two = lambda x: 1 << x
lcm = lambda a, b: a * b // gcd(a, b)

def solve():
	(n, m) = mulinp()
	a = arrinp()
	l = []
	d = defaultdict(lambda : 0)
	s = defaultdict(lambda : set())
	pairs = m
	for i in range(m):
		(x, y) = mulinp()
		d[x - 1] += 1
		s[x - 1].add(y - 1)
		d[y - 1] += 1
		s[y - 1].add(x - 1)
	if pairs % 2 == 0:
		print(0)
		return
	ans = sys.maxsize
	for i in d:
		if d[i] % 2:
			ans = min(ans, a[i])
		else:
			for j in s[i]:
				if d[j] % 2 == 0:
					ans = min(ans, a[i] + a[j])
	print(ans)

def main():
	tc = intinp()
	while tc:
		solve()
		tc -= 1
main()


test = int(input())
while test:
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	adj = dict()
	for i in range(m):
		(x, y) = map(int, input().split())
		if x in adj:
			adj[x][0] += 1
			adj[x].append(y)
		else:
			adj[x] = [1, y]
		if y in adj:
			adj[y][0] += 1
			adj[y].append(x)
		else:
			adj[y] = [1, x]
	if m % 2:
		ans1 = ans2 = float('inf')
		for (i, j) in adj.items():
			if j[0] % 2:
				ans1 = min(ans1, a[i - 1])
			else:
				for k in range(1, len(j)):
					if adj[j[k]][0] % 2 == 0:
						ans2 = min(ans2, a[i - 1] + a[j[k] - 1])
		print(min(ans1, ans2))
	else:
		print(0)
	test -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	e = []
	for _ in range(m):
		e.append(list(map(int, input().split())))
	if m % 2 == 0:
		print(0)
	else:
		ans = float('inf')
		d = {i: 0 for i in range(n)}
		for (a, b) in e:
			d[a - 1] += 1
			d[b - 1] += 1
		for i in range(n):
			if d[i] % 2 == 1:
				ans = min(ans, l[i])
		for (a, b) in e:
			a -= 1
			b -= 1
			if (d[a] + d[b]) % 2 == 0:
				ans = min(ans, l[a] + l[b])
		if ans < float('inf'):
			print(ans)
		else:
			ans = 0
			for i in range(n):
				if d[i] > 0:
					ans += l[i]
			print(ans)


t = int(input())
for i in range(t):
	[n, m] = [int(i) for i in input().split()]
	uval = ['faltu']
	uval += [int(i) for i in input().split()]
	dict = {}
	for i in range(1, n + 1):
		dict[i] = 0
	arr = []
	arr2 = []
	for i in range(m):
		[x, y] = [int(i) for i in input().split()]
		arr2.append(uval[x] + uval[y])
		dict[x] += 1
		dict[y] += 1
		arr.append([x, y])
	arr1 = []
	if m % 2 == 0:
		print(0)
	else:
		for i in arr:
			x = i[0]
			y = i[1]
			if dict[x] % 2 == 1 and dict[y] % 2 == 1:
				arr1.append(min(uval[x], uval[y]))
			elif dict[x] % 2 == 1 and dict[y] % 2 == 0:
				arr1.append(uval[x])
			elif dict[x] % 2 == 0 and dict[y] % 2 == 1:
				arr1.append(uval[y])
			elif (dict[x] + dict[y] - 1) % 2 == 1:
				arr1.append(uval[x] + uval[y])
		if arr1 != []:
			print(min(arr1))
		else:
			print(min(arr2))


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	g = [[] for _ in range(n)]
	for _ in range(m):
		(x, y) = [int(x) - 1 for x in input().split()]
		g[x].append(y)
		g[y].append(x)
	if m % 2 == 0:
		print(0)
	else:
		mi = 1000000000.0
		for i in range(n):
			cl = len(g[i])
			if cl % 2 == 1:
				mi = min(mi, a[i])
			else:
				for j in range(cl):
					if len(g[g[i][j]]) % 2 == 0:
						mi = min(a[i] + a[g[i][j]], mi)
		if mi == -1:
			print(sum(a))
		else:
			print(mi)


from collections import defaultdict
from functools import reduce

def party(n, m, array, adj):
	if not m % 2:
		return 0
	odds = [i for i in range(1, n + 1) if len(adj[i]) % 2]
	if odds:
		minodd = array[reduce(lambda x, y: x if array[x] <= array[y] else y, odds)]
	else:
		minodd = 10 ** 10
	mineven = 10 ** 10
	evens = [i for i in range(1, n + 1) if not len(adj[i]) % 2]
	for e1 in evens:
		for e2 in [i for i in adj[e1] if not len(adj[i]) % 2]:
			mineven = min(mineven, array[e1] + array[e2])
	return min(minodd, mineven)
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	array = [0] + list(map(int, input().split(' ')))
	adj = defaultdict(lambda : [])
	for _ in range(m):
		(x, y) = map(int, input().split(' '))
		adj[x].append(y)
		adj[y].append(x)
	print(party(n, m, array, adj))


import functools

def main():
	n_tests = int(input())
	for _ in range(n_tests):
		(n, m) = list(map(int, input().split(' ')))
		u = list(map(int, input().split(' ')))
		friends = {}
		pairs = set()
		for _ in range(m):
			(x, y) = list(map(int, input().split(' ')))
			if x not in friends:
				friends[x] = []
			if y not in friends:
				friends[y] = []
			friends[x].append(y)
			friends[y].append(x)
			pairs.add(tuple(sorted((x, y))))
		arr = []
		for (i, loss) in enumerate(u):
			cnt = friends.get(i + 1, [])
			arr.append((loss, len(cnt)))
		if m % 2 == 0:
			print('0')
			continue
		result = float('inf')
		for (i, d) in enumerate(arr):
			(loss, t_cn) = d
			if t_cn % 2 == 1:
				result = min(result, loss)
		for (x, y) in list(pairs):
			if arr[x - 1][1] % 2 == 0 and arr[y - 1][1] % 2 == 0:
				result = min(result, u[x - 1] + u[y - 1])
		print(result)
main()


from collections import defaultdict

def dfs(node):
	val = 0
	for i in friend[node]:
		if i in sett:
			val += ai[i - 1]
	return val
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ai = list(map(int, input().split()))
	ais = list(sorted(ai))
	friend = defaultdict(list)
	for _ in range(m):
		(x, y) = map(int, input().split())
		friend[x].append(y)
		friend[y].append(x)
	if m % 2 == 0:
		print(0)
		continue
	ans = 1e+18
	for i in range(1, n + 1):
		if len(friend[i]) % 2:
			ans = min(ans, ai[i - 1])
	for i in range(1, n + 1):
		for ii in friend[i]:
			ans = min(ans, ai[i - 1] + ai[ii - 1])
	print(ans)


from collections import defaultdict
from sys import maxsize
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	cc_by_member = [0 for i in range(n)]
	adj_list = defaultdict(list)
	cc = 0
	pairs = []
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		a -= 1
		b -= 1
		cc += 1
		cc_by_member[a] += 1
		cc_by_member[b] += 1
		adj_list[a].append(b)
		adj_list[b].append(a)
		pairs.append((a, b))
	if cc % 2 == 0:
		print(0)
	else:
		remove_odd_cost = maxsize
		rm_even_even = maxsize
		cand = [i for i in range(len(cc_by_member)) if cc_by_member[i] % 2]
		if cand:
			remove_odd_cost = arr[min(cand, key=lambda x: arr[x])]
		p = [pair for pair in pairs if cc_by_member[pair[0]] % 2 == 0 and cc_by_member[pair[1]] % 2 == 0]
		if p:
			rm_even_even = min(p, key=lambda z: arr[z[0]] + arr[z[1]])
			rm_even_even = arr[rm_even_even[0]] + arr[rm_even_even[1]]
		print(min(remove_odd_cost, rm_even_even))