#include <bits/stdc++.h>
 
using namespace std;
 
const int MaxN = (int)5e4 + 10;
const int ROOT = 1;
 
int n, en, c[MaxN], ptr;
long long ans[MaxN], sz[MaxN];
int in[MaxN], out[MaxN], timer;
long long fenwp[MaxN], fenwc[MaxN];
vector < long long > edge[MaxN];
vector < pair < int, int > > g[MaxN];
vector < vector < long long > > downSize, upSize;
vector < pair < long long, int > > vin[MaxN], vout[MaxN];
vector < pair < pair < int, int >, pair < long long, int > > > queries;
 
long long calcBinarySearch(const vector < vector < long long > > &f, long long R, long long sign) {
	if (f.empty()) {
		return 0LL;
	}
	long long res = 0;
	int sz = (int)f.size();
	int l = 0, r = sz - 1, p = -1;
	while (l <= r) {
		int m = (l + r) / 2;
		if ((f[m][0] - R / 2) * sign <= 0) {
			p = m;
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	if (sign == +1) {
		res += 2 * (p >= 0 ? f[p][2] : 0LL) + R * (f[sz - 1][1] - (p >= 0 ? f[p][1] : 0LL)) - f[sz - 1][2];
	} else {
		res += -2 * (p >= 0 ? f[p][2] : 0LL) + R * (p >= 0 ? f[p][1] : 0LL) + f[sz - 1][2];
	}
	return res;
}
 
void dfs(int v, int p) {
	in[v] = ++timer;
	sz[v] = c[v];
	for (auto to : g[v]) {
		if (to.first == p) {
			continue;
		}
		dfs(to.first, v);
		sz[v] += sz[to.first];
	}
	out[v] = timer;
}
 
void dfsSolve(int v, int p, int e = 0) {
	if (p > 0) {
		edge[in[v]] = {sz[v], e};
	} else {
		edge[in[v]] = {0, 0};
	}
	for (int i = 0; i < (int)g[v].size(); ++i) {
		pair < int, int > to = g[v][i];
		if (to.first == p) {
			continue;
		}
		long long L = sz[to.first], R = sz[ROOT] - sz[to.first];
		queries.push_back(make_pair(make_pair(in[to.first], out[to.first]), make_pair(L, ++ptr)));
		if (1 <= in[to.first] - 1) {
			queries.push_back(make_pair(make_pair(1, in[to.first] - 1), make_pair(R, ptr)));
		}
		if (out[to.first] + 1 <= n) {
			queries.push_back(make_pair(make_pair(out[to.first] + 1, n), make_pair(R, ptr)));
		}
		ans[ptr] -= calcBinarySearch(downSize, R, -1);
		ans[ptr] += calcBinarySearch(upSize, R, 1);
		downSize.push_back({sz[to.first], to.second, 1LL * sz[to.first] * to.second});
		if (downSize.size() > 1) {
			downSize[downSize.size() - 1][1] += downSize[downSize.size() - 2][1];
			downSize[downSize.size() - 1][2] += downSize[downSize.size() - 2][2];
		}
		upSize.push_back({sz[ROOT] - sz[to.first], to.second, 1LL * (sz[ROOT] - sz[to.first]) * to.second});
		if (upSize.size() > 1) {
			upSize[upSize.size() - 1][1] += upSize[upSize.size() - 2][1];
			upSize[upSize.size() - 1][2] += upSize[upSize.size() - 2][2];
		}
		dfsSolve(to.first, v, to.second);
		downSize.pop_back();
		upSize.pop_back();
	}
}
 
template < class T >
void upd(T fenw[], int r, T val) {
	while (r <= n) {
		fenw[r] += val;
		r |= r + 1;
	}
}
 
template < class T > 
T get(T fenw[], int r) {
	T ans = T(0);
	while (r >= 0) {
		ans += fenw[r];
		r &= r + 1, --r;
	}
	return ans;
}
 
int fnd(const vector < long long >& idx, long long x) {
	return upper_bound(idx.begin(), idx.end(), x) - idx.begin() - 1;
}
 
void Process(const vector < pair < pair < int, int >, pair < long long, int > > >& queries) {
	vector < long long > toCompress;
	for (int i = 1; i <= n; ++i) {
		toCompress.push_back(edge[i][0]);
	}
	sort(toCompress.begin(), toCompress.end());
	toCompress.resize(unique(toCompress.begin(), toCompress.end()) - toCompress.begin());
	for (auto it : queries) {
		int l = it.first.first, r = it.first.second, where = it.second.second;
		long long k = it.second.first;
		vin[l].push_back(make_pair(k, where));
		vout[r].push_back(make_pair(k, where));
	}
	long long b01 = 0, b1 = 0;
	for (int i = 1; i <= n; ++i) {
		for (auto it : vin[i]) {
			long long k = it.first;
			int where = it.second, p = fnd(toCompress, k / 2);
			ans[where] -= 2 * get(fenwp, p) + k * (b1 - get(fenwc, p)) - b01;
		}
		b01 += edge[i][0] * edge[i][1];
		b1 += edge[i][1];
		upd(fenwp, fnd(toCompress, edge[i][0]), edge[i][0] * edge[i][1]);
		upd(fenwc, fnd(toCompress, edge[i][0]), edge[i][1]);
		for (auto it : vout[i]) {
			long long k = it.first;
			int where = it.second, p = fnd(toCompress, k / 2);
			ans[where] += 2 * get(fenwp, p) + k * (b1 - get(fenwc, p)) - b01;
		}
	}
	for (int i = 0; i <= n; ++i) {
		vin[i].clear();
		vout[i].clear();
		fenwp[i] = fenwc[i] = 0;
	}
}
 
void solve() {
	scanf("%d", &n);
	en += n;
	assert (2 <= n && n <= 50000 && en <= 250000);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &c[i]);
		assert (1 <= c[i] && c[i] <= 50000);
	}
	for (int i = 0; i < n - 1; ++i) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		assert (x != y);
		assert (1 <= x && x <= n);
		assert (1 <= y && y <= n);
		assert (1 <= w && w <= 50000);
		g[x].push_back(make_pair(y, w));
		g[y].push_back(make_pair(x, w));
	}
	dfs(ROOT, 0);
	dfsSolve(ROOT, 0);
	Process(queries);
	long long answer = (1ULL << 63) - 1;
	assert (ptr == n - 1);
	assert (timer == n);
	for (int i = 1; i < n; ++i) {
		answer = min(answer, ans[i]);
	}
	printf("%lld\n", answer);
	for (int i = 1; i <= n; ++i) {
		g[i].clear();
		edge[i].clear();
		ans[i] = 0;
	}
	queries.clear();
	timer = ptr = 0;
}
 
int main() {
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	int t;
	scanf("%d", &t);
	assert (1 <= t && t <= 250000);
	while (t --> 0) {
		solve();
	}
	return 0;
}