Author : Kamonasish Roy
Tester : Abu Sufian Rafi
Editorial :

• Key Observations

Whenever you add an edge between U and V, the resulting cycle consists of the original path P from U to V plus the new edge whose cost equals the sum of costs along P. Therefore the total edge‐cost on the cycle is 2 × (sum of C_e over e∈P). The total node‐weight on the cycle is (sum of W_i over nodes i∈P). Hence for any two nodes U, V the cycle weight is
(sum of W along path U–V) − 2 × (sum of C along path U–V).

You cannot choose two nodes that are already adjacent—if the optimal pair were directly connected, that would form a 2‐node cycle, but that edge already exists and is disallowed. Thus the best path must consist of at least two edges.

• Reduction to “Best Path” Problem on a Tree

Define for each node u a DP value dp[u] equal to the maximum, over all downward paths starting at u, of
(sum of W along that path) − 2 × (sum of C along that path).

Then the answer will either be:

• the best cycle that “turns” at some node u, using two distinct downward branches of u (ensuring at least two edges in the cycle);

• or a single downward path from the root extended twice, but those would correspond to picking two nodes in the same branch (which also works as long as they’re not direct parent/child).

Final calculation :
For each node u, we maintain a value
dp[u] = W[u] plus the maximum (over all children v of u) of
max(0, dp[v] − 2·C[u][v]).

In other words, dp[u] represents the best achievable “(sum of node‑weights) minus twice (sum of edge‑costs)” along any downward path starting at u.

At the same time, for each node u we track the two largest non‑negative contributions
Δ[v] = max(0, dp[v] − 2·C[u][v])
coming from its neighbors v.

The best cycle that “turns” at u (i.e. uses two distinct subtrees of u, so its endpoints aren’t adjacent) has weight
W[u] + (largest Δ[v]) + (second‑largest Δ[v]).

Therefore the overall answer is the maximum, over all nodes u, of
W[u] + top‑1 Δ + top‑2 Δ.

Time Complexity: O(N)

Code(C++) :

#include<bits/stdc++.h>
using namespace std;
const long long M=5e5,MOD=1e9+7;
typedef long long ll;

ll dp[M][2];
ll w[M];
ll res;
vector<pair<int,ll>>Edge[M];
ll cost[M];
void dfs(int x,int p){
	for(auto it:Edge[x]){
		if(it.first!=p){
			cost[it.first]=it.second;
			dfs(it.first,x);
		}
	}
	res=max(res,dp[x][0]+dp[x][1]-w[x]);
    if(dp[x][0]==-1e12){
    	ll cur=w[x]+w[p]-(2LL * cost[x]);
    	if(dp[p][0]<=cur){
    		swap(dp[p][0],dp[p][1]);
    		dp[p][0]=cur;
    	}
    	else{
    		dp[p][1]=max(dp[p][1],cur);
    	}
    }
    else{
    	if(p!=0){
    		ll cur=w[p]+w[x]-(2LL * cost[x]);
    		ll cur_1=dp[x][0]+w[p]-(2LL * cost[x]);
    		res=max(res,cur_1);
    		cur=max(cur,cur_1);
    		if(dp[p][0]<=cur){
    			swap(dp[p][0],dp[p][1]);
    		    dp[p][0]=cur;
    		}
    		else{
    			dp[p][1]=max(dp[p][1],cur);
    		}
    		
    	}
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)cin>>w[i];
    	for(int i=1;i<n;i++){
    		int x,y;
    		ll z;
    		cin>>x>>y>>z;
    		Edge[x].push_back({y,z});
    		Edge[y].push_back({x,z});
    	}
    	for(int i=0;i<=n;i++){
    		dp[i][0]=dp[i][1]=-1e12;
    		cost[i]=0;
    	}
    	res=-1e18;
    	dfs(1,0);
    	cout<<res<<"\n";
    	for(int i=1;i<=n;i++)Edge[i].clear();
    	
    	
    	
    	}
    	
    	   
    return 0;
 
}