#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <climits>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <iomanip>

#define ALL(v) v.begin(), v.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REPD(i, a, b) for(int i = a; i > b; i--)
#define REPLL(i, a, b) for(ll i = a; i < b; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FORLL(i, a, b) for(ll i = a; i <= b; i++)
#define INF 1000000001

#define vit vector<int>::iterator
#define sit set<int>::iterator
#define vi vector<int>
#define vpii vector<pii >

#define ll long long
#define ld long double

#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pld pair<ld, ld>
#define st first
#define nd second

#define EPS 1e-9
#define PI acos(-1.0)
#define MAXN 40

using namespace std;

int z, n, m, a, b;
int gold[MAXN];
vi nbs[MAXN];
vi nbsf[MAXN];
int dist[MAXN];
vi ls[MAXN];
int layers;
int cl[MAXN];
int vis[MAXN];
int mark[MAXN];
int ret, x;

void bfs() {
    queue<int> q;
    q.push(0);
    REP(i, 0, n) dist[i] = INF;
    dist[0] = 0;
    while(q.size()) {
        int c = q.front(); q.pop();
        ls[dist[c]].pb(c);
        REP(i, 0, nbs[c].size()) {
            int nb = nbs[c][i];
            if(dist[nb] == INF) {
                dist[nb] = dist[c] + 1;
                q.push(nb);
            }
        }
    }
    layers = dist[1];
    cl[layers] = 1;
    cl[0] = 0;
}

int dfs_back(int v) {
    if(v == 0) return 1;
    if(vis[v]++) return 0;
    if(mark[v]) return 0;
    REP(i, 0, nbs[v].size()) {
        if(dfs_back(nbs[v][i])) return 1;
    }
    return 0;
}

void fl(int layer, int cur, int bag) {
    if(layer == layers) {
        if(cur == 1 && bag > ret) {
            memset(vis, 0, sizeof vis);
            if(dfs_back(1)) {
                //FOR(i, 0, layers) cout << cl[i] << " "; cout << endl;
                ret = max(ret, bag);
            }
        }
        return;
    }
    REP(i, 0, nbsf[cur].size()) {
        int nxt = nbsf[cur][i];
        mark[nxt] = 1;
        cl[layer+1] = nxt;
        bag += gold[nxt];
        fl(layer+1, nxt, bag);
        mark[nxt] = 0;
        cl[layer+1] = -1;
        bag -= gold[nxt];
        fl(layer+1, nxt, bag);
    }
}

int main()
{
	scanf("%d", &z); z++;

	while(z-- > 1) {
        scanf("%d%d", &n, &m);
        ret = 0;
        FOR(i, 0, n) {
            nbs[i].clear();
            nbsf[i].clear();
            ls[i].clear();
        }
        memset(cl, -1, sizeof cl);
        memset(mark, 0, sizeof mark);
        memset(vis, 0, sizeof vis);

        REP(i, 2, n) scanf("%d", &gold[i]);
        REP(i, 0, m) {
            scanf("%d%d", &a, &b);
            --a; --b;
            nbs[a].pb(b);
            nbs[b].pb(a);
        }
        bfs();
        REP(i, 0, n) {
            REP(j, 0, (int)nbs[i].size()) {
                int nb = nbs[i][j];
            }
            REP(j, 0, (int)nbs[i].size()) {
                int nb = nbs[i][j];
                if(dist[nb] > dist[i]) nbsf[i].pb(nb);
            }
        }
        fl(0, 0, 0);
        printf("%d\n", ret);
	}

    return 0;
}