#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,a[N],val[1<<N];

int main() {
    int T;
    for(scanf("%d",&T); T--;) {
        scanf("%d",&n);
        for(int i=0; i<n; ++i)scanf("%d",&a[i]);
        for(int S=0; S<(1<<n); ++S) {
            val[S]=0;
            for(int i=0; i<n; ++i)if(S>>i&1)val[S]+=a[i];
        }
        int ans=0;
        for(int S=1<<n; S; S--)
            for(int S2=S; S2; S2=(S2-1)&S)
                if(val[S2]==val[S^S2])ans=max(ans,val[S2]);
        printf("%d\n",val[(1<<n)-1]-ans*2);
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<map>

using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1000+10;
int f[N],n,m;
struct Edge
{
    int u,v,c;
    bool operator<(const Edge& b)
    {
        return c<b.c;
    }
} e[3000+300];

int Find(int x)
{
    return f[x]==x?x:f[x]=Find(f[x]);
}

int Kruscal()
{
    int mini=INF;
    for(int k=0; k<m; ++k)
    {
        int cnt=0,lowb=INF,upb=~INF;
        for(int i=1; i<=n; ++i)
            f[i]=i;
        for(int i=k; i<m; ++i)
        {
            int u=e[i].u,v=e[i].v,c=e[i].c;
            if(Find(u)!=Find(v))
            {
                f[Find(u)]=Find(v);
                cnt++;
                lowb=min(lowb,c);
                upb=max(upb,c);
                if(cnt==n-1)
                {
                    mini=min(mini,upb-lowb);
                    break;
                }
            }
        }
    }
    return mini==INF?-1:mini;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; ++i)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
    sort(e,e+m);
    printf("%d\n",Kruscal());
    return 0;
}