#include <iostream>
using namespace std;
const int MAXN = 200005;
vector<pair<int, int>> adj[MAXN];
vector<long long> weights(MAXN), depth(MAXN), totalWeight(MAXN);
void dfs(int node, int parent) {
    totalWeight[node] = weights[node];
    for (auto [next, cost] : adj[node]) {
        if (next == parent) continue;
        depth[next] = depth[node] + cost;
        dfs(next, node);
        totalWeight[node] += totalWeight[next];
    }
}
int main() {
    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;
        for (int i = 1; i <= N; ++i) {
            cin >> weights[i];
            adj[i].clear();
        }
        for (int i = 0; i < N - 1; ++i) {
            int u, v, c;
            cin >> u >> v >> c;
            adj[u].push_back({v, c});
            adj[v].push_back({u, c});
        }
        depth.assign(N + 1, 0);
        dfs(1, 0);
        long long maxCycleWeight = LLONG_MIN;
        for (int u = 1; u <= N; ++u) {
            for (int v = u + 1; v <= N; ++v) {
                // Use depth to calculate cost of path from u to v
                long long cost = depth[u] + depth[v];
                long long cycle = totalWeight[u] + totalWeight[v] - cost;
                maxCycleWeight = max(maxCycleWeight, cycle);
            }
        }
        cout << maxCycleWeight << '\n';
    }
    return 0;
}