wa #9 #10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll c[114514],w[114514],z[114514];
int h[114514],e[214514],ne[214514],idx;
ll f[114514],ans,res;
int st[114514];

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

inline ll dfs(int x,ll op)
{
	ll cnt=0;
	st[x]=1;
	for(int i=h[x];i;i=ne[i])
	{
		int y=e[i];
		if(!st[y])
		{
			z[x]+=dfs(y,op+w[i]);
			
		}
	}
	z[x]+=c[x];
	f[1]+=op*c[x];
	return z[x];
}

inline void fdfs(int x)
{
	st[x]=1;
	for(int i=h[x];i;i=ne[i])
	{
		int y=e[i];
		if(!st[y])
		{
			f[y]=f[x]-z[y]*w[i]+(res-z[y])*w[i];
			ans=min(ans,f[y]);
			fdfs(y);
		}
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i];
		res+=c[i];
	}
	  
	  
	for(int i=1;i<=n-1;i++)  
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);	
		
	}
	//cout<<res<<' ';
	st[1]=1;
	for(int i=h[1];i;i=ne[i])
	{
		int y=e[i];
		z[1]+=dfs(y,w[i]);
	}
	z[1]+=c[1];
	ans=f[1];
	memset(st,0,sizeof st);
	st[1]=1;
	for(int i=h[1];i;i=ne[i])
	{
		int y=e[i];
		f[y]=f[1]-z[y]*w[i]+(res-z[y])*w[i];
		ans=min(ans,f[y]);
		fdfs(y);
		//cout<<y<<' '<<f[y]<<' '<<z[y]<<' '<<w[i]<<' '<<res<<'\n';
	}
	//for(int i=1;i<=n;i++)
	  //cout<<f[i]<<' ';
	cout<<ans;
	//cout<<z[2]<<" "<<z[4];
	return 0;
}