#include<bits/stdc++.h>
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define ceil(pp,qq) (((pp)>0)^((qq)>0)?-Abs(pp)/Abs(qq):(pp)%(qq)?(pp)/(qq)+1:(pp)/(qq))
#define floor(pp,qq) (((pp)>0)^((qq)>0)?-ceil(Abs(pp),Abs(qq)):(pp)/(qq))
#define ll long long
#define LL __int128
using namespace std;
ll Abs(ll x){return x > 0 ? x : - x;}
inline ll read(){
	char ch = getchar();
	ll s = 0; bool w = 0;
	while(!isdigit(ch)){if(ch == '-')w = 1;ch = getchar();}
	while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	return w ? - s : s;
}

const int itinf = 1e9;
const ll llinf = 4e18;
const int mod = 1000000007;
const int N = 500009;

inline int mul(int nma, int nmb){
	return ((1ll * nma * nmb % mod) + mod) % mod;
}

void solve(){
	int n = read(), lst = 0;
	ll ans = 0;
	vector<ll>c(n), dp(n), dfn(n);
	vector<vector<int>>g(n), dset(n);
	vector<array<int, 24>>fa(n), minc(n);
	irep(i,0,n - 1)c[i] = minc[i][0] = read();
	irep(i,1,n - 1){
		int u = read() - 1, v = read() - 1;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	auto dfs = [&](auto self, int x) -> void{
//		cerr << x << ' ' << endl;
		dfn[x] = lst ++;
		dset[dp[x]].push_back(x);
		for(int y : g[x]){
			if(y != 0 && dp[y] == 0){
				dp[y] = dp[x] + 1;
				fa[y][0] = x;
				self(self, y);
			}
		}
	};
		
	dfs(dfs, 0);
//	cerr << fa[3][0];
	for(int r = 1; r <= 23; ++ r){
		for(int i = 0; i < n; ++ i){
			fa[i][r] = fa[fa[i][r - 1]][r - 1];
			if((i + (1 << (r - 1))) > n)minc[i][r] = minc[i][r - 1];
			else minc[i][r] = min(minc[i][r - 1], minc[i + (1 << (r - 1))][r - 1]);
		}
	}
	
	auto rmq = [&](int l, int r) -> ll{
swap(l, r);
		if(l > r)return llinf;
//		swap(l, r);
		
		int len = r - l + 1, pw = __lg(len);
		return min(minc[l][pw], minc[r - (1 << pw) + 1][pw]);
	};
	
	auto lca = [&](int x, int y) -> int{
		if(x == y)return x;
		if(dp[x] < dp[y])swap(x, y);
		for(int r = 23; r >= 0; -- r){
			if(dp[fa[x][r]] >= dp[y])x = fa[x][r];
		}
		if(x == y)return x;
		for(int r = 23; r >= 0; -- r){
			if(fa[x][r] != fa[y][r]){
				x = fa[x][r] , y = fa[y][r];
			}
		}
		return fa[x][0];
	};
	for(int i = 1; i < n; ++ i){
		if(dset[i].size()){
			dset[i].push_back(0);
			sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
		}
		else break;
		
		int sz = dset[i].size();
		for(int j = 0; j + 1 < sz; ++ j){
			dset[i].push_back(lca(dset[i][j], dset[i][j + 1]));
		}
		
		sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
		dset[i].erase(unique(dset[i].begin(), dset[i].end()), dset[i].end());

	//	cerr << "PRINT dset\n";
	//	for(int hh : dset[i])cerr << hh << ' ';
	//	cerr << endl;		
	
		vector<array<int, 2>>edge;
		vector<vector<int>>tree;
		sz = dset[i].size();
		map<int,int> idx, fd;

		for(int j = 0; j + 1 < sz; ++ j){
			int lc = lca(dset[i][j], dset[i][j + 1]);
			edge.push_back({lc, dset[i][j + 1]});
			if(idx.find(lc) == idx.end())
				idx[lc] = idx.size(), fd[idx[lc]] = dp[lc];
			if(idx.find(dset[i][j + 1]) == idx.end())
				idx[dset[i][j + 1]] = idx.size(),
				fd[idx[dset[i][j + 1]]] = dp[dset[i][j + 1]];
		}

		tree.resize(idx.size());

		for(auto [x, y] : edge){
			int u = idx[x], v = idx[y];
			tree[u].push_back(v);
			tree[v].push_back(u);
		//	cerr << u << ' ' << v << endl;
		}
	//	cerr << endl;
		vector<ll>f(idx.size(), llinf);
		auto work = [&](auto self, int x, int fax) -> void{
			/*
				i -> depth
				cost = a[depth - dp[u]] or sum f[v]
				i - (fd[u])
				i - (fd[fax] + 1)
			*/
			f[x] = rmq(i - fd[x], i - fd[fax] - 1);
			if(i == fd[x])return;

			ll alt = 0;
			for(int y : tree[x]){
				if(fd[y] > fd[x]){
					self(self, y, x);
					alt += f[y];
				}
			}
		//	cout << "Dt " << i - fd[x] <<  ' ' << f[x] << ' ' << alt << endl;;
			f[x] = min(f[x], alt);
			
			
		};
		work(work, 0, 0);
		ans += f[0];
	//	cout << "F= " << f[0] << endl;
	//	cout << endl;
	}
	//cout << endl;
	printf("%lld\n", ans + c[0]);
}

int main(){
	int T = read();
	while(T --){
		solve();
	}
	return 0;
}