#include <bits/stdc++.h>
using namespace std;


long long inf = numeric_limits<long long>::max()/3;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //ifstream cin("input.txt");
    long long t;
    cin>>t;
    while (t--){
        long long n;
        cin>>n;
        vector<long long> nums(n);
        for (long long i=0;i<n;i++){
            long long num;
            cin>>num;
            nums[i] = num;
        }

        vector<vector<long long>> adj_matrix(n+1,vector<long long>(n+1,inf));
        vector<vector<long long>> adj_list(n+1);
        for (long long i=0;i<=n;i++){
            adj_matrix[i][i] = 0;
        }

        for (long long i=0;i<n;i++){
            long long a,b;
            cin>>a>>b;
            adj_matrix[a-1][b-1] = 1;
            adj_matrix[b-1][a-1] = 1;
            adj_list[a-1].push_back(b-1);
            adj_list[b-1].push_back(a-1);
        }

        if (n==1){
            cout<<nums[0]<<"\n";
            continue;
        }
        for (long long k=0;k<=n;k++){
            for (long long i=0;i<=n;i++){
                for (long long j=0;j<=n;j++){
                    if (adj_matrix[i][k] + adj_matrix[k][j] < adj_matrix[i][j]){
                        adj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j];
                    }
                }
            }
        }

        vector<vector<long long>> garbage3(n+1,vector<long long>(n+1));
        vector<vector<long long>> garbage2(n+1,vector<long long>(n+1));
        vector<vector<long long>> garbage1(n+1,vector<long long>(n+1));
        for (long long i=0;i<=n;i++){
            for (long long j=0;j<=n;j++){
                for (long long k=0;k<=n;k++){
                    if (adj_matrix[i][k]+adj_matrix[j][k]!=adj_matrix[i][j] && abs(adj_matrix[i][k]-adj_matrix[j][k])!=adj_matrix[i][j]){
                        garbage3[i][j]++;
                    }
                    if (adj_matrix[i][k]+adj_matrix[j][k]!=adj_matrix[i][j] && adj_matrix[k][j]-adj_matrix[k][i]!=adj_matrix[i][j]){
                        garbage1[i][j]++;
                    }
                    if (adj_matrix[i][k]+adj_matrix[j][k]!=adj_matrix[i][j] && adj_matrix[k][i]-adj_matrix[k][j]!=adj_matrix[i][j]){
                        garbage2[i][j]++;
                    }
                }
            }
        }
        //index in nums, left, right, mask
        //0: no expansion, 1: expand to left, 2: expand to right, 3: expand to both
        vector<vector<vector<vector<long long>>>> dp(n+1,vector<vector<vector<long long>>>(n+1,vector<vector<long long>>(n+1,vector<long long>(4))));
        vector<vector<vector<vector<bool>>>> reached(n+1,vector<vector<vector<bool>>>(n+1,vector<vector<bool>>(n+1,vector<bool>(4))));
        for (long long j=0;j<=n;j++){
            for (long long k=0;k<=n;k++){
                if (adj_matrix[j][k]==2){
                    reached[0][j][k][3] = true;
                }
            }
        }
        for (long long i=0;i<n;i++){
            for (long long j=0;j<=n;j++){
                for (long long k=0;k<=n;k++){
                    for (long long mask=0;mask<=3;mask++){
                        if (!reached[i][j][k][mask]){
                            continue;
                        }
                        
                        if (mask==3){
                            dp[i+1][j][k][1] = max(dp[i+1][j][k][1],dp[i][j][k][3] + nums[i]);
                            dp[i+1][j][k][2] = max(dp[i+1][j][k][2],dp[i][j][k][3] + nums[i]);
                            reached[i+1][j][k][1] = true;
                            reached[i+1][j][k][2] = true;
                        }else if (mask==2){
                            dp[i+1][j][k][0] = max(dp[i+1][j][k][0],dp[i][j][k][2] + nums[i]);
                            reached[i+1][j][k][0] = true;
                        }else if (mask==1){
                            dp[i+1][j][k][0] = max(dp[i+1][j][k][0],dp[i][j][k][1] + nums[i]);
                            reached[i+1][j][k][0] = true;
                        }


                        if (mask==0){                 
                            dp[i+1][j][k][0] = max(dp[i+1][j][k][0],dp[i][j][k][0]);
                            reached[i+1][j][k][0] = true;
                        }else if (mask==1){
                            if (garbage1[j][k]-(i+1-adj_matrix[j][k])>=1){
                                dp[i+1][j][k][1] = max(dp[i+1][j][k][1],dp[i][j][k][1]);
                                reached[i+1][j][k][1] = true;
                            }
                            for (long long child:adj_list[j]){
                                if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
                                    dp[i+1][child][k][1] = max(dp[i+1][child][k][1],dp[i][j][k][1] + nums[i]);
                                    reached[i+1][child][k][1] = true;
                                }
                            }
                        }else if (mask==2){
                            if (garbage2[j][k]-(i+1-adj_matrix[j][k])>=1){
                                dp[i+1][j][k][2] = max(dp[i+1][j][k][2],dp[i][j][k][2]);
                                reached[i+1][j][k][2] = true;
                            }
                            
                            for (long long child:adj_list[k]){
                                if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
                                    dp[i+1][j][child][2] = max(dp[i+1][j][child][2],dp[i][j][j][2] + nums[i]);
                                    reached[i+1][j][child][2] = true;
                                }
                            }
                        }else{
                            if (garbage3[j][k]-(i-(adj_matrix[j][k]-2))>=1){
                                dp[i+1][j][k][3] = max(dp[i+1][j][k][3],dp[i][j][k][3]);
                                reached[i+1][j][k][3] = true;
                            }
                            for (long long child:adj_list[j]){
                                if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
                                    dp[i+1][child][k][3] = max(dp[i+1][child][k][3],dp[i][j][k][3] + nums[i]);
                                    reached[i+1][child][k][3] = true;
                                }
                            }
                            for (long long child:adj_list[k]){
                                if (adj_matrix[j][child]+adj_matrix[child][k]!=adj_matrix[j][k]){
                                    dp[i+1][j][child][3] = max(dp[i+1][j][child][3],dp[i][j][j][3] + nums[i]);
                                    reached[i+1][j][child][3] = true;
                                }
                            }
                        }
                        //cout<<i<<" "<<j<<" "<<k<<" "<<mask<<" "<<dp[i][j][k][mask]<<endl;
                    }
                }
            }
        }

        long long answer = 0;
        for (long long i=0;i<=n;i++){
            for (long long j=0;j<=n;j++){
                answer = max(dp[n][i][j][0],answer);
            }
        }
        cout<<answer<<"\n";
    }
    return 0;
}