随机化骗了40分。。。

// luogu-judger-enable-o2
//code by rainman
#include<cstdio>
#include<cstdlib>
#define Rand(N) (int)((double)rand()/RAND_MAX*(N))
using namespace std;

const int MAXN = 1e5+10;
const int MAXM = MAXN;
int head[MAXN],tot;
int n,c[MAXN],dep[MAXN];
bool vis[MAXN],used[MAXN];
int ans=0x7fffffff;

struct Edge{
    int v,w,next;
}edge[MAXM<<1];

void addedge(int x,int y,int z)
{
    edge[++tot].v=y;
    edge[tot].w=z;
    edge[tot].next=head[x];
    head[x]=tot;
}

void dfs(int x)
{
    vis[x]=true;
    for(int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].v;
        if(vis[y])continue;
        dep[y]=dep[x]+edge[i].w;
        vis[y]=true;dfs(y);
    }
}

int main()
{
    srand(19260817);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=n-1;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
        addedge(y,x,z);
    }
    
    for(int i=1;i<=4444;i++)
    {
        int x=1+Rand(n)%n;
        if(used[x])continue;
        used[x]=true;
        for(int j=1;j<=n;j++)
        vis[j]=false,dep[j]=0;
        dfs(x); int temp=0;
        for(int j=1;j<=n;j++)
        temp+=(dep[j]*c[j]);
        if(temp<ans)ans=temp;
    }
    
    printf("%d",ans);
    return 0;
}