#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
int d[N];//每个点的度数
int x[N],y[N];
int a[N];//每个人的不满值
int ans=INT_MAX;
int t;
int main()
{  cin.tie(0);
   ios::sync_with_stdio(false);
   
   cin>>t;
   while(t--)
   {
     cin>>n>>m;
   for(int i=1;i<=n;i++)
   {
      cin>>a[i],d[i]=0;
   }
  for(int i=1;i<=m;i++)
  {
   cin>>x[i]>>y[i];
   ++d[x[i]],++d[y[i]];
  }
   if(m%2==0)
   {
      cout<<0<<endl;
      continue;
   }
   for(int i=1;i<=n;i++)//删除一个点的情况
      if(d[i]%2==1)
         ans=min(ans,a[i]);
      
   
   //删除两个点
   for(int i=1;i<=m;i++)
   {
      if((d[x[i]]+d[y[i]])%2==0)
      {
         ans=min(ans,a[x[i]]+a[y[i]]);
      }
   }
   cout<<ans<<endl;
   }
   
   return 0;

}
# ```