#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define lson t[pos].ls #define rson t[pos].rs #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=500010,N=1010,M=1000,inf=1e18; struct Edge{int v,nx,w;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v,int w){edge[++CNT]={v,h[u],w};h[u]=CNT;edge[++CNT]={u,h[v],w};h[v]=CNT;} int n,m,ans,a[MAXN]; // vector<pii>G[MAXN]; struct node{ int pri,sz,siz,sum,ls,rs; pii x; int lz; bool lz2; }t[MAXN]; int cnt; mt19937 rng(time(0)); struct treap{ int rt; void upd(int pos,int x,bool y){ if(y){ t[pos].x.fr=-t[pos].x.fr,t[pos].lz=-t[pos].lz,t[pos].lz2^=1; t[pos].sum=-t[pos].sum; swap(lson,rson); } t[pos].x.fr+=x; t[pos].lz+=x; t[pos].sum+=x*t[pos].sz; } void pushdown(int pos){ if(lson)upd(lson,t[pos].lz,t[pos].lz2); if(rson)upd(rson,t[pos].lz,t[pos].lz2); t[pos].lz=t[pos].lz2=0; } void pushup(int pos){ t[pos].sz=t[lson].sz+t[rson].sz+t[pos].x.sc; t[pos].siz=t[lson].siz+t[rson].siz+1; t[pos].sum=t[lson].sum+t[rson].sum+t[pos].x.fr*t[pos].x.sc; } int nnd(pii x){ t[++cnt]={rng(),x.sc,1,x.fr*x.sc,0,0,x,0,0}; return cnt; } pii split(int pos,int key){ if(!pos)return mk(0,0); pushdown(pos); if(t[pos].x.fr<=key){ pii tmp=split(rson,key); rson=tmp.fr; pushup(pos); return mk(pos,tmp.sc); } else{ pii tmp=split(lson,key); lson=tmp.sc; pushup(pos); return mk(tmp.fr,pos); } } pii sblit(int pos,int key){ if(!pos)return mk(0,0); pushdown(pos); // cout<<" "<<t[pos].x.fr<<","<<t[pos].x.sc<<" "<<key<<" "<<t[lson].sz<<" "<<t[rson].sz<<endl; if(t[lson].sz+t[pos].x.sc<=key){ pii tmp=sblit(rson,key-t[lson].sz-t[pos].x.sc); rson=tmp.fr; pushup(pos); return mk(pos,tmp.sc); } else if(t[lson].sz<key){ int tmp=nnd(mk(t[pos].x.fr,key-t[lson].sz)); t[pos].x.sc-=key-t[lson].sz; t[tmp].ls=t[pos].ls,t[pos].ls=0; pushup(tmp),pushup(pos); return mk(tmp,pos); } else{ pii tmp=sblit(lson,key); lson=tmp.sc; pushup(pos); return mk(tmp.fr,pos); } } int mrge(int x,int y){ if(!x||!y)return x|y; pushdown(x),pushdown(y); if(t[x].pri<t[y].pri){ t[x].rs=mrge(t[x].rs,y); pushup(x); return x; } else{ t[y].ls=mrge(x,t[y].ls); pushup(y); return y; } } pii fid(int pos){ if(!pos)return mk(inf,inf); pushdown(pos); if(!lson)return t[pos].x; return fid(lson); } void cut(int x){ rt=split(rt,x).fr; } void cut2(int x){ rt=sblit(rt,x).fr; } void upd(int x){ upd(rt,x,1); } void add(int k){ int x=rt,y=k;rt=0; if(fid(x)>fid(y))swap(x,y); while(x&&y){ pii tmp=split(x,fid(y).fr); rt=mrge(rt,tmp.fr),x=tmp.sc; swap(x,y); } if(x||y)rt=mrge(rt,x|y); } void insert(pii x){ rt=mrge(rt,nnd(x)); } }T[MAXN]; void dfs(int u,int lst){ int mn=inf; for(inx(u))mn=min(mn,w); for(inx(u))if(v!=lst){ dfs(v,u); T[v].upd(w),T[v].cut(mn); T[u].add(T[v].rt); } T[u].cut2(a[u]); if(t[T[u].rt].sz<a[u])T[u].insert(mk(mn,a[u]-t[T[u].rt].sz)); ans+=t[T[u].rt].sum; } void slv(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<n;i++){ int u=read(),v=read(),w=read(); add_side(u,v,w); } dfs(1,1); printf("%lld",ans); } signed main(){ // freopen("d.in","r",stdin);freopen("d.out","w",stdout); // int _=read();while(_--) slv(); // cerr<<(clock()*1.0/CLOCKS_PER_SEC)<<"s\n"; return 0; }