#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]; struct func { ll k,b; }; func F(func a,func b){ //b.k(a.kx+a.b)+b.b return {b.k*a.k,b.k*a.b+b.b}; } int rt[maxn]; struct fhq_treap { int tot; struct node { int pos; int ls,rs,rnd; ll dt; ll siz,sdt,sdt0,sp,spdt; func lz; node(){lz={1,0};} void push(func k){ if(k.k==-1)swap(ls,rs); lz=F(lz,k); sp*=k.k;sp+=k.b*siz; spdt*=k.k;spdt+=k.b*sdt; pos=k.k*pos+k.b; } }d[int(3e6)+10]; void pu(int p){ d[p].siz=1,d[p].sdt=d[p].dt,d[p].sdt0=max(-d[p].dt,0ll),d[p].sp=d[p].pos,d[p].spdt=d[p].sp*d[p].dt; d[p].siz+=d[d[p].ls].siz+d[d[p].rs].siz; d[p].sdt+=d[d[p].ls].sdt+d[d[p].rs].sdt; d[p].sdt0+=d[d[p].ls].sdt0+d[d[p].rs].sdt0; d[p].sp+=d[d[p].ls].sp+d[d[p].rs].sp; d[p].spdt+=d[d[p].ls].spdt+d[d[p].rs].spdt; }int nnd(int x){ int p=++tot; d[p].rnd=rand(),d[p].pos=x;pu(p); return p; } void pd(int p){ if(d[p].ls)d[d[p].ls].push(d[p].lz); if(d[p].rs)d[d[p].rs].push(d[p].lz); d[p].lz={1,0}; } void spl(int u,int k,int &p,int &q){ if(!u)return p=q=0,void();pd(u); if(d[u].pos<=k)p=u,spl(d[u].rs,k,d[p].rs,q),pu(p); else q=u,spl(d[u].ls,k,p,d[q].ls),pu(q); } int mg(int x,int y){ if((!x)||(!y))return x|y;pd(x),pd(y); if(d[x].rnd<d[y].rnd){ d[x].rs=mg(d[x].rs,y);pu(x);return x; }else { d[y].ls=mg(x,d[y].ls);pu(y);return y; } } void add(int &rt,int x,int v){ int p=0,q=0,r=0; spl(rt,x-1,p,q),spl(q,x,q,r); if(!q)q=nnd(x); d[q].dt+=v;pu(q); rt=mg(mg(p,q),r); } int S[maxn],tp; void dfs(int u){ if(!u)return; S[++tp]=u;pd(u); if(d[u].ls)dfs(d[u].ls); if(d[u].rs)dfs(d[u].rs); d[u].ls=d[u].rs=0; pu(u); } void ins(int &p,int q){ add(p,d[q].pos,d[q].dt); } void merge(int &p,int q,int m){ if(d[p].siz>=d[q].siz){ d[q].push((func){-1,m}); tp=0;dfs(q); up(i,1,tp)ins(p,S[i]); }else { d[q].push((func){-1,m}); tp=0;dfs(p); up(i,1,tp)ins(q,S[i]); p=q; } } void sp(int u,int k,int &p,int &q){ if(!u)return p=q=0,void();pd(u); if(k>=d[d[u].ls].siz+1)p=u,sp(d[u].rs,k-d[d[u].ls].siz-1,d[p].rs,q),pu(p); else q=u,sp(d[u].ls,k,p,d[q].ls),pu(q); } int find(int &u){ int p=0; sp(u,d[u].siz-1,u,p); return p; } }T; ll S[maxn]; void get(int u){ ll res=T.d[rt[u]].sdt*1ll*mn[u]-T.d[rt[u]].spdt; S[u]+=res; } void dfs(int u,int fa){ for(auto it:E[u]){ int x=it.p1,w=it.p2; if(x==fa)continue; dfs(x,u); S[u]+=S[x]; int xx=0; T.spl(rt[x],w,rt[x],xx); T.merge(rt[u],rt[x],w); } ll nw=T.d[rt[u]].sdt0; nw-=w[u]; if(nw>=0){T.add(rt[u],0,w[u]); int loc=0; while(rt[u]){ int x=T.find(rt[u]); loc=T.d[x].pos; nw+=min(T.d[x].dt,0ll);if(nw<0)break; } if(rt[u])T.add(rt[u],loc,nw); }else T.add(rt[u],0,w[u]); //cout<<u<<" "<<"S="<<S[u]<<endl; int xx=0; T.spl(rt[u],mn[u],rt[u],xx); get(u); ll S=T.d[rt[u]].sdt; T.add(rt[u],mn[u],-S); } 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; }