#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 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,f[N][N],a[MAXN]; vector<pii>G[MAXN]; void dfs(int u,int lst){ int sum=0,mn=inf; for(inx(u))mn=min(mn,w); for(inx(u))if(v!=lst){ dfs(v,u); int tmp=0; for(auto o:G[v])if(w-o.fr<=mn)G[u].pb(mk(w-o.fr,o.sc)),sum+=o.sc; sort(G[u].begin(),G[u].end()); } while(sum>a[u]){ if(a[u]<=sum-G[u].back().sc)sum-=G[u].back().sc,G[u].pop_back(); else G[u].back().sc-=sum-a[u],sum=a[u]; } if(sum<a[u])G[u].pb(mk(mn,a[u]-sum)); int ls=0,now=a[u],res=0; for(auto o:G[u]){ res+=(o.fr-ls)*now,now-=o.sc; ls=o.fr; // cout<<o.fr<<" "<<now<<" "<<res<<endl; } ans+=res; // ans+=G[u].back().fr*a[u]; } 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; }