#include<bits/stdc++.h>
using namespace std;
long long T,n,a[205],hd[405],idx,ver[405],nxt[405],vis[405],len[405],sum;
void add(long long x,long long y){
    ver[++idx]=y;
    nxt[idx]=hd[x];
    hd[x]=idx;
}
//1:n,2:n*(n-1),3:n*(n-1)*(n-2);
void dfs(long long xx,long long x,long long ch){
    len[xx]=max(len[xx],ch);
    vis[x]=1;
    for (long long i=hd[x];i;i=nxt[i]){
        long long y=ver[i];
        if (vis[y]==0){
            vis[y]=1;
            dfs(xx,y,ch+1);
        }
    }
}
bool cmp(long long x,long long y){
    return x>y;
}
int main(){
    freopen("Paimon.in","r",stdin);
    freopen("Paimon.out","w",stdout);
    cin>>T;
    while(T--){
        idx=0,sum=0;
        memset(hd,0,sizeof(hd));
        memset(nxt,0,sizeof(nxt));
        memset(ver,0,sizeof(ver));
        memset(len,0,sizeof(len));
        cin>>n;
        for (long long i=1;i<=n;i++){
            cin>>a[i];
        }
        for (long long i=1;i<=n;i++){
            long long x,y;
            cin>>x>>y;
            add(x,y);
            add(y,x);
        }
        for (long long i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            dfs(i,i,0);
        }
        sort(a+1,a+1+n,cmp);
        sort(len+1,len+1+n,cmp);
        for (long long i=1;i<=len[1];i++){
            sum+=a[i];
        }
        cout<<sum<<endl;
    }
    return 0;
}