#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back typedef long long ll; using namespace std; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,w[maxn],mn[maxn]; vector<pi>E[maxn]; map<ll,ll> q[maxn]; ll S[maxn]; void get(int u){ vector<pi>v; for(auto it:q[u]){ if(it.p1<=mn[u])v.p_b(it); } ll res=0; ll s=0; up(i,0,(int)v.size()-1){ s+=v[i].p2; res+=v[i].p2*1ll*(mn[u]-v[i].p1); } S[u]+=res; } void dfs(int u,int fa){ ll nw=0; for(auto it:E[u]){ int x=it.p1,w=it.p2; if(x==fa)continue; dfs(x,u); S[u]+=S[x]; for(auto p=q[x].rbegin();p!=q[x].rend();p++){ auto it=*p; if(w>=it.p1){ q[u][w-it.p1]+=it.p2,nw+=max(-it.p2,0ll); } } } if(u==3){ //cout<<"!!! "<<u<<endl; //for(auto it:q[u])cout<<"+ "<<it.p1<<" "<<it.p2<<endl; } nw-=w[u]; //if(u==3)cout<<"???? "<<nw<<" "<<q[u][0]<<endl; if(nw>=0){ q[u][0]+=w[u]; vector<int>del; int loc=0; for(auto it=q[u].rbegin();it!=q[u].rend();it++){ auto x=*it; del.p_b(x.p1),loc=x.p1; nw+=min(x.p2,0ll);if(nw<0)break; }for(auto it:del)q[u].erase(it); if(q[u].size())q[u][loc]+=nw; }else q[u][0]+=w[u]; //cout<<u<<" "<<"S="<<S[u]<<endl; get(u); while(q[u].size()&&(*(--q[u].end())).p1>mn[u])q[u].erase((*(--q[u].end())).p1); //cout<<u<<" "<<S[u]<<" "<<endl; ll S=0;for(auto it:q[u])S+=it.p2; q[u][mn[u]]-=S; //cout<<u<<" "<<S[u]<<endl; //cout<<"size "<<u<<" "<<q[u].size()<<endl; { //cout<<"!!! "<<u<<endl; //for(auto it:q[u])cout<<"+ "<<it.p1<<" "<<it.p2<<endl; } } void slv(){ n=read(); up(i,1,n)w[i]=read(),mn[i]=1e9; up(i,1,n-1){ int x=read(),y=read(),w=read(); mn[x]=min(mn[x],w),mn[y]=min(mn[y],w); E[x].p_b(m_p(y,w)),E[y].p_b(m_p(x,w)); } dfs(1,0); cout<<S[1]; } int main(){ //freopen("d.in","r",stdin),freopen("d.out","w",stdout); slv(); fclose(stdin),fclose(stdout); return 0; }