#include<bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb                          push_back
#define all(x)                      (x).begin(),(x).end()
#define ll                          long long
#define ld                          long double
#define eps                         1e-9
#define sz(a)                       (ll)(a).size()
#define ppc                         __builtin_popcount
#define ppcll                       __builtin_popcountll
#define endl                        "\n"
#define lb                          lower_bound
#define ub                          upper_bound
const ld PI = acos(-1.0);
const int MOD = 1e9 +7;
const ll INF = 1e18;
// if(abs(a-b)<eps) --> if(a==b)
// fixed << setprecision(n) -->printing decimal till n
// hypot(a ,b) --> sqrt(a^2 + b^2)
using namespace std;

void solve(){
    ll n ,m;
    cin>>n>>m;
    vector<ll>A(n);
    for(int i=0;i<n;i++){
        cin>>A[i];
    }

    set<pair<ll,ll>>s;
    unordered_map<ll,ll>mp1;
    vector<pair<ll,ll>>mpp;
    for(int i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        s.insert({a ,b});
        mp1[a]++;
        mp1[b]++;
    }

    if(m%2==0){
        cout<<0<<endl;
        return;
    }
    else{
        //the one with smallest happinness in this m array
        //we have to not take them both
        ll ans =INF;
        for(auto it:mp1){
            if(it.second&1){
                //by deletig this we remian with an even pair
                ans = min(ans, A[it.first]);
            }
        }

        //we can delete that also which sums to an odd
        //check for any 2
        for(auto it:s){
            if((mp1[it.first] + mp1[it.second] -1)&1){
                ans = min(ans , A[it.first] + A[it.second] );
            }
        }
        cout<<ans<<endl;
    }


}

int main(){
    IO;
    ll t =1;
    cin>>t;
    for(int i=1;i<=t;i++){
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}