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

using ll = long long;

struct Edge {
    int to;
    ll cost;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<ll> W(N);
        for (int i = 0; i < N; i++) cin >> W[i];

        vector<vector<Edge>> adj(N);
        for (int i = 0; i < N-1; i++) {
            int u,v; ll c;
            cin >> u >> v >> c;
            u--; v--;
            adj[u].push_back({v,c});
            adj[v].push_back({u,c});
        }

        vector<ll> depth(N,0), parent(N,-1);
        vector<ll> weightSum(N,0), costSum(N,0);

        function<void(int,int)> dfs = [&](int u,int p){
            for (auto &e : adj[u]) {
                if (e.to == p) continue;
                parent[e.to] = u;
                depth[e.to] = depth[u]+1;
                weightSum[e.to] = weightSum[u] + W[e.to];
                costSum[e.to] = costSum[u] + e.cost;
                dfs(e.to,u);
            }
        };

        weightSum[0] = W[0];
        dfs(0,-1);

        vector<ll> F(N);
        for (int i = 0; i < N; i++) {
            F[i] = weightSum[i] - 2*costSum[i];
        }

        // Compute max F in subtree of u
        vector<ll> maxF_subtree(N, LLONG_MIN);
        function<void(int,int)> dfs2 = [&](int u,int p){
            ll cur = F[u];
            for (auto &e : adj[u]){
                if (e.to == p) continue;
                dfs2(e.to,u);
                cur = max(cur, maxF_subtree[e.to]);
            }
            maxF_subtree[u] = cur;
        };
        dfs2(0,-1);

        vector<ll> maxF_outside(N, LLONG_MIN);
        maxF_outside[0] = LLONG_MIN;

        // Reroot to get maxF outside subtree
        function<void(int,int,ll)> dfs3 = [&](int u,int p,ll val){
            maxF_outside[u] = val;
            // Collect maxF_subtree of children
            vector<ll> prefix, suffix;
            vector<int> children;
            for (auto &e : adj[u]){
                if (e.to == p) continue;
                children.push_back(e.to);
            }
            int m = (int)children.size();
            prefix.resize(m);
            suffix.resize(m);
            for (int i=0; i<m; i++){
                prefix[i] = maxF_subtree[children[i]];
                if (i>0) prefix[i] = max(prefix[i], prefix[i-1]);
            }
            for (int i=m-1; i>=0; i--){
                suffix[i] = maxF_subtree[children[i]];
                if (i+1<m) suffix[i] = max(suffix[i], suffix[i+1]);
            }
            for (int i=0; i<m; i++){
                int c = children[i];
                ll left = (i==0) ? LLONG_MIN : prefix[i-1];
                ll right = (i==m-1) ? LLONG_MIN : suffix[i+1];
                ll use = val;
                use = max(use, left);
                use = max(use, right);
                use = max(use, F[u]);
                dfs3(c,u,use);
            }
        };

        dfs3(0,-1,LLONG_MIN);

        ll ans = LLONG_MIN;
        for (int u=0; u<N; u++){
            for (auto &e : adj[u]){
                int v = e.to;
                if (parent[v] == u){
                    ll cand = maxF_subtree[v] + maxF_outside[v];
                    ans = max(ans, cand);
                }
            }
        }

        // Also check single node F(u) if no edges yield better
        for (int i=0; i<N; i++){
            ans = max(ans, F[i]);
        }

        cout << ans << "\n";
    }
}