from collections import defaultdict
from sys import stdin
input = stdin.buffer.readline
def func():
if m % 2 == 0:
print(0)
else:
odd = list(x for x in range(1, n+1) if len(friends[x]) % 2 != 0)
even = list(x for x in range(1, n+1) if len(friends[x]) % 2 == 0)
first = 10**9
second = 10**9
if even:
for f in even:
for e in friends[f]:
first = min(first, a[f-1] + a[e-1])
if second:
for f in odd:
second = min(second, a[f-1])
print(min(first, second))
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
friends = defaultdict(list)
for __ in range(m):
x, y = map(int, input().split())
friends[x].append(y)
friends[y].append(x)
func()
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define MAXN 100010
int x[MAXN], y[MAXN], a[MAXN], degree[MAXN];
int n, m;
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
degree[i] = 0;
cin >> a[i];
}
for (int i = 1; i <= m; i++)
{
cin >> x[i] >> y[i];
degree[x[i]]++;
degree[y[i]]++;
}
int ans = INT_MAX;
if (m % 2 == 0)
ans = 0;
for (int i = 1; i <= n; i++)
if (degree[i] % 2 == 1)
ans = min(ans, a[i]);
for (int i = 1; i <= m; i++)
if (degree[x[i]] % 2 == 0 && degree[y[i]] % 2 == 0)
ans = min(ans, a[x[i]] + a[y[i]]);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
206. Reverse Linked List | 83. Remove Duplicates from Sorted List |
116. Populating Next Right Pointers in Each Node | 145. Binary Tree Postorder Traversal |
94. Binary Tree Inorder Traversal | 101. Symmetric Tree |
77. Combinations | 46. Permutations |
226. Invert Binary Tree | 112. Path Sum |
1556A - A Variety of Operations | 136. Single Number |
169. Majority Element | 119. Pascal's Triangle II |
409. Longest Palindrome | 1574A - Regular Bracket Sequences |
1574B - Combinatorics Homework | 1567A - Domino Disaster |
1593A - Elections | 1607A - Linear Keyboard |
EQUALCOIN Equal Coins | XOREQN Xor Equation |
MAKEPAL Weird Palindrome Making | HILLSEQ Hill Sequence |
MAXBRIDGE Maximise the bridges | WLDRPL Wildcard Replacement |
1221. Split a String in Balanced Strings | 1002. Find Common Characters |
1602A - Two Subsequences | 1555A - PizzaForces |