AC:39/WA:57

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10,M=N*2,inf=1e18;
int h[N],e[M],ne[M],w[M],idx;
int X[N];
int value[N];
int dep[N];
int n;
PII Minv[N];
namespace dsu
{
	int p[N];
	void init()
	{
		for(int i=1;i<=n;i++) p[i]=i;
	}
	int find(int x)
	{
		if(x!=p[x]) return p[x]=find(p[x]);
		return p[x];
	}
	bool merge(int x,int y)
	{
		int px=find(x),py=find(y);
		if(px==py) return false;
		p[px]=py;
		return true;
	}
};

struct F
{
	int u1,u2;
	int val(int x)
	{
		return value[x];
	}
	void update(int x)
	{
		if(!x) return;
		if(!u1) u1=x;
		else if(value[x]<=value[u1])
		{
			if(dsu::find(x)==dsu::find(u1)) u1=x;
			else u2=u1,u1=x;
		}
		else if(!u2||(dsu::find(x)!=dsu::find(u1)&&value[x]<=value[u2])) 
		{
			u2=x;
		}
	}
}f[N];

struct G
{
	int minv1,u1,minv2,u2;
	void update(int minv,int x)
	{
		if(!x) return;
		if(minv<=minv1) 
		{
			if(dsu::find(x)==dsu::find(u1)) minv1=minv,u1=x;
			else minv2=minv1,u2=u1,minv1=minv,u1=x;
		}
		else if(!u2||(dsu::find(x)!=dsu::find(u1)&&minv<=minv2)) minv2=minv,u2=x;
	}
}g[N];

void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dfs(int u,int fa)
{
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(v==fa) continue;
		dep[v]=dep[u]+w[i];
		dfs(v,u);
	}
}

void dfs1(int u,int fa)
{
	f[u]={0,0},g[u]={inf,0,inf,0};
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(v==fa) continue;
		dfs1(v,u);
		f[u].update(f[v].u1),f[u].update(f[v].u2);
		f[u].update(v);
	}
}

void dfs2(int u,int fa)
{
	if(f[u].u1) g[u].update(value[f[u].u1]-2*dep[u],f[u].u1);
	if(f[u].u2) g[u].update(value[f[u].u2]-2*dep[u],f[u].u2);
	for(int i=h[u];~i;i=ne[i])
	{
		int v=e[i];
		if(v==fa) continue;
		if(g[u].u1) g[v].update(g[u].minv1,g[u].u1);
		if(g[u].u2) g[v].update(g[u].minv2,g[u].u2);
		g[v].update(value[u]-2*dep[u],u);
		dfs2(v,u);
	} 
}

int boruvka()
{
	int sum=0;
	dsu::init();
	bool flag=true;
	while(flag)
	{
		flag=false;
		dfs1(1,0);
		dfs2(1,0);
		for(int i=1;i<=n;i++) Minv[i]={inf,0};
		for(int u=1;u<=n;u++) 
		{	
			//printf("%d %d %d\n",u,f[u].u1,f[u].u2);
			if(!g[u].u1) continue;
			int pa=dsu::find(u);
			if(g[u].u1!=u&&dsu::find(g[u].u1)!=pa) Minv[pa]=min(Minv[pa],(PII){g[u].minv1+value[u],g[u].u1});
			else if(g[u].u2) Minv[pa]=min(Minv[pa],(PII){g[u].minv2+value[u],g[u].u2});
		}
		
		for(int i=1;i<=n;i++)
		{
			if(!Minv[i].second) continue;
			int w=Minv[i].first,x=Minv[i].second;
			if(dsu::merge(i,x)) sum+=w,flag=true;
		}
	}
	
	return sum;
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	
	memset(h,-1,sizeof h);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>X[i];
		
	for(int i=1,a,b,c;i<n;i++)
	{
		cin>>a>>b>>c;
		add(a,b,c),add(b,a,c);
	}
	
	dfs(1,0);
	for(int i=1;i<=n;i++) value[i]=dep[i]+X[i];
	
	cout<<boruvka()<<"\n";
	
	return 0;
}

有信用！