#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define LL long long
#define maxn 100005

using namespace std;

int T,v,E,cnt,pre[maxn];
LL c[maxn],d[maxn];
struct edge
{
    int u,v,next;
    LL d;
};
edge e[maxn<<1];

void addedge(int u,int v,LL dis)
{
    e[cnt].u=u; e[cnt].v=v; e[cnt].d=dis;
    e[cnt].next=pre[u]; pre[u]=cnt++;
}

void spfa(int st)
{
    queue<int> q;
    while (!q.empty()) q.pop();
    bool vis[maxn];
    memset(vis,0,sizeof(vis));

    q.push(st); vis[st]=1; d[st]=0;
    while (!q.empty())
    {
        int u=q.front(); q.pop();
        vis[u]=0;
        for (int i=pre[u];i!=-1;i=e[i].next)
        {
            int v=e[i].v;
            if (d[v]==-1 || d[v]>d[u]+e[i].d)
            {
                d[v]=d[u]+e[i].d;
                if (!vis[v])
                {
                    vis[v]=1; q.push(v);
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(c,0,sizeof(c));
        memset(e,0,sizeof(e)); cnt=0;
        memset(d,-1,sizeof(d));
        memset(pre,-1,sizeof(pre));
        int a,b; LL dis;

        scanf("%d%d",&v,&E);

        for (int i=0;i<v;i++) scanf("%I64d",&c[i]);
        for (int i=0;i<E;i++)
        {
            scanf("%d%d%I64d",&a,&b,&dis);
            addedge(a,b,dis); addedge(b,a,dis);
        }
        spfa(1);

        LL ans=0; bool f=0;
        for (int i=1;i<=v;i++)
        {
            if (d[i]==-1)
            {
                f=1;
                break;
            }
            ans+=d[i]*c[i-1];
        }
        if (f) printf("No Answer\n");
        else printf("%I64d\n",ans);
    }
    return 0;
}