題目看著向生成樹，但實(shí)際上是最短路徑+堆優(yōu)化。
#include <stdio.h>

const int LEN = 50005;
const __int64 MAX = 0x7fffffffffffffff; 

struct HEAD
{
    int next;
    int last;
    __int64 dis;
    int used;
}head[LEN];

struct NODE
{
    int num;
    __int64 len;
    int next;
}node[LEN*2];
int next;

//堆部分
int hash[LEN]; //堆中部分現(xiàn)在所在的位置
struct HEAP
{
    int num; //指向堆外面
    __int64 dis;
}heap[LEN];
int hlen; //堆大小

__int64 weight[LEN]; //記錄重量

inline void init ( int v )
{

    hlen = 0;
    next = 0;
    for ( int i=0; i<v; i++ )
    {
        head[i].dis = MAX;
        head[i].next = -1;
        head[i].used = 0;
    }
}

void ins ( int a, int b, __int64 len )
{

    node[next].num = b;
    node[next].next = -1;
    node[next].len = len;
    next ++;

    if ( head[a].next==-1 )
        head[a].next = next-1;
    else
        node[ head[a].last ].next = next-1;
    head[a].last = next-1;
}

inline void swap ( int a, int b )
{

    struct
    {
        __int64 dis;
        int num;
    }temp;

    temp.dis = heap[a].dis;
    temp.num = heap[a].num;
    heap[a].dis = heap[b].dis;
    heap[a].num = heap[b].num;
    heap[b].dis = temp.dis;
    heap[b].num = temp.num;
}

inline void moveup ( int p )
{

    while ( p>0&&heap[(p-1)/2].dis>heap[p].dis )
    {
        hash[ heap[p].num ] = (p-1)/2;
        hash[ heap[ (p-1)/2 ].num ] = p;
        swap ( p, (p-1)/2 );
        p = (p-1)/2;
    }
}

inline void movedown ( int p )
{

    int flag = 1;
    while ( p<hlen&&flag )
    {
        int lson = p*2+1;
        int rson = p*2+2;
        flag = 0;
        if ( rson<hlen )
        {
            if ( heap[lson].dis<=heap[rson].dis&&heap[lson].dis<heap[p].dis )
            {
                hash[ heap[p].num] = lson;
                hash[ heap[lson].num] = p;
                swap ( p, lson );
                p = lson;
                flag = 1;
            }
            else if ( heap[rson].dis<=heap[lson].dis&&heap[rson].dis<heap[p].dis )
            {
                hash[ heap[p].num] = rson;
                hash[ heap[rson].num] = p;
                swap ( p, rson );
                p = rson;
                flag = 1;
            }
        }
        else if ( lson<hlen )
        {
            if ( heap[lson].dis<heap[p].dis )
            {
                hash[ heap[p].num] = lson;
                hash[ heap[lson].num] = p;
                swap ( p, lson );
                p = lson;
                flag = 1;
            }
        }
    }
}

void dj ( int s, int n )
{

    head[s].dis = 0;
    for ( int i=0; i<n; i++ )
    {
        heap[hlen].dis = head[i].dis;
        heap[hlen].num = i;
        hlen ++;
        hash[i] = hlen-1;
        moveup ( hlen-1 );
    }
    for ( int i=0; i<n-1; i++ )
    {
        __int64 min0;
        int min1;
        min0 = heap[0].dis;
        min1 = heap[0].num;
        if ( min0==MAX )
            return;
        head[min1].used = 1;
        int tmp = heap[hlen-1].num;
        hash[tmp] = 0;
        hash[min1] = hlen-1;
        swap ( 0, hlen-1 );
        hlen--;
        moveup ( hash[tmp] );
        movedown ( hash[tmp] );
        for ( int j=head[min1].next; j!=-1; j=node[j].next )
        {
            int e = node[j].num;
            __int64 t_dis = head[min1].dis+node[j].len;
            if ( t_dis<head[e].dis )
            {
                head[e].dis = t_dis;
                heap[hash[e]].dis = t_dis;
                moveup ( hash[e] );
            }
        }
    }
}

int main ()
{

    int t;
    scanf ( "%d", &t );
    while ( t-- )
    {
        int v, e;
        scanf ( "%d%d", &v, &e );
        for ( int i=0; i<v; i++ )
            scanf ( "%I64d", &weight[i] );
        init ( v );
        for ( int i=0; i<e; i++ )
        {
            int a, b;
            __int64 len;
            scanf ( "%d%d%I64d", &a, &b, &len );
            if ( a!=b )
            {
                ins ( a-1, b-1, len );
                ins ( b-1, a-1, len );
            }
        }

        dj ( 0, v );
        __int64 ans = 0;
        for ( int i=0; i<v; i++ )
        {
            if ( head[i].dis==MAX )
            {
                ans = -1;
                break;
            }
            ans += head[i].dis*weight[i];
        }
        if ( ans==-1 )
            printf ( "No Answer\n" );
        else
            printf ( "%I64d\n", ans );
    }
    return 0;
}