KCM城即将迎来圣诞节。在KCM市，忠诚的平民苏比正在准备一棵整洁的圣诞树。
树的简单结构如右图所示。树可以表示为编号节点和一些边的集合。节点编号为1到n。
根始终编号为1。树中的每个节点都有其权重。权重可以彼此不同
。另外，两个节点之间每个可用边的形状都不同，因此每个边的单价也不同。
由于技术上的困难，一条边的价格将是（所有后代节点的权重之和）×（边的单价）。
在所有可能的选择中，苏比希望最小化整棵树的成本。他还想使用所有节点
，因为他想要一棵大树。所以他决定请你帮他解决这个问题，找到最低成本。
Input
输入由T个测试用例组成。测试用例的数量T在输入文件的第一行中给出。
每个测试用例由几行组成。两个数字v，e（0≤ v、 e≤ 50000）在每个测试用例的第一行中给出。
在下一行中，在一行中给出了表示v节点权重的v正整数wi
。在下面的e行上，每行包含三个正整数a、b、c，表示能够连接两个节点a和b的边，以及单价c。
输入中的所有数字都小于2^16。
Output
对于每个测试用例，在一行中输出一个整数，指示树的最小可能成本。如果无法制作圣诞树，
请在一行中打印“No Answer”。
Sample Input
2
2 1
1 1
1 2 15
7 7
200 10 20 30 40 50 60
1 2 1
2 3 3
2 4 2
3 5 4
3 7 2
3 6 3
1 5 9
Sample Output
15
1210

N与M一个级别，稀疏图用临界表，朴素版n^2超时
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue> 
using namespace std;

typedef long long LL;
typedef pair<LL,int>PLI;
#define INF 1LL<<61
const int N=5e5+10;
LL weight[N];
LL h[N],e[N],ne[N],w[N],idx;
LL dist[N];
bool st[N];
int v,E;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
    for(int i=0;i<=v;i++)
    {
        dist[i]=INF;
    }
    memset(st,false,sizeof st);
    dist[1]=0;
    priority_queue<PLI,vector<PLI>,greater<PLI>>heap;
    PLI d;
    d.first=0,d.second=1;
    heap.push(d);
    while(heap.size())
    {
        PLI t=heap.top();
        heap.pop();
        int ver=t.second;
        LL dis=t.first;
        if(st[ver])continue;
        st[ver]=true;
        for(LL i=h[ver];i!=-1;i=ne[i])
        {
            LL j=e[i];
            if(dist[j]>dist[ver]+w[i])
            {
                dist[j]=dist[ver]+w[i];
                d.first=dist[j],d.second=j;
                heap.push(d);
            }
        }
    }
}
int main()
{
    LL T;
    scanf("%lld",&T);

    while(T--)
    {

        scanf("%d%d",&v,&E);
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=1;i<=v;i++)
        {
            scanf("%lld",&weight[i]);
        }
        int a,b;LL c;
        while(E--)
        {
            scanf("%d%d%lld",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        if (v == 0 || v == 1) {
            puts("0");
            continue;
        }
        dijkstra();
        LL sum=0;
        int flag=0;
        for(int i=2;i<=v;i++)
        {
            if(dist[i]==INF)
            {
                flag=1;
                break;
            }
            sum+=dist[i]*weight[i];         
        }
        if(flag==1)
        {
            printf("No Answer\n");
        }
        else
        {
            printf("%lld\n",sum);
        }
    }
    return 0;
}