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

#define int long long
const int INF = 1e18;

int los(tuple<int, int, int> a) {
	return get<0>(a) - min(get<0>(a), get<1>(a));
}

bool cmp(tuple<int, int, int> a, tuple<int, int, int> b) {
	return los(a) < los(b);
}

tuple<int, int, int> go(int now, int prv, vector<vector<int>> &adj, vector<int> &a) {
	// 1: this node is picked
	// 2: this node is not picked, covered
	// 3: this node is not covered

	// 1 --> all child take min(1, 2, 3) + cost
	// 2 --> one child takes 1, all takes min(1, 2)
	// 3 --> all child take min(1, 2)

	vector<tuple<int, int, int>> chz;
	for (int u: adj[now]) {
		if (u != prv) {
			chz.push_back(go(u, now, adj, a));
		}
	}

	int ans1 = a[now];
	for (auto [x, y, z]: chz) {
		ans1 += min(x, min(y, z));
	}

	int ans2 = 0;
	if (chz.empty()) ans2 = INF;
	else {
		sort(chz.begin(), chz.end(), cmp);
		ans2 += get<0>(chz[0]);
		for (int i = 1; i < chz.size(); i++) {
			ans2 += min(get<0>(chz[i]), get<1>(chz[i]));
		}
	}

	int ans3 = 0;
	for (auto [x, y, z]: chz) {
		ans3 += min(x, y);
	}

	return {ans1, ans2, ans3};
}

void solve() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<vector<int>> adj(n);
	for (int i = 1; i < n; i++) {
		int x, y; cin >> x >> y;
		x--, y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	auto [v1, v2, v3] = go(0, 0, adj, a);
	cout << min(v1, v2) << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int t; cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}