所有数据都查了，范围也够了，双边也加了，就是WA！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<memory.h>
using namespace std;
#define Maxn 1600090
#define Inf 2000000000
#define FILL(a,h) memset(a,(h),sizeof(a))
#define FOR(i,l,r) for(int i=l;i<=r;i++)
typedef long long LL;
typedef unsigned long long ULL;

struct node1{int v,next;LL w;}g[Maxn*3];
int T,n,m,cnt,W[Maxn],p[Maxn];
LL dis[Maxn];
bool vis[Maxn];

inline void addEdge(int u,int v,ULL c){
	g[cnt].v=u,g[cnt].w=c,g[cnt].next=p[v],p[v]=cnt++;
}
void SPFA(void){
	FOR(i,1,n)dis[i]=Inf; dis[1]=0;
	FILL(vis,0); vis[1]=true;
	queue<LL> q; q.push(1);
	while(!q.empty()){
		int now=q.front(); q.pop(); vis[now]=0;
		for(int e=p[now];e!=-1;e=g[e].next){
			if(dis[g[e].v]>dis[now]+g[e].w){
				dis[g[e].v]=dis[now]+g[e].w;
				if(!vis[g[e].v]){q.push(g[e].v);vis[g[e].v]=true;}
			}
		}
	}
}
int main(int argc,char**argv){
	for(scanf("%d",&T);T--;){
		int u,v,c;
		FILL(p,-1); cnt=0;
		scanf("%d%d",&n,&m);
		FOR(i,1,n)scanf("%d",&W[i]);
		FOR(i,1,m){
			scanf("%d%d%I64u",&u,&v,&c);
			addEdge(u,v,c);
			addEdge(v,u,c);
		}
		SPFA();
		//FOR(i,1,n)printf("%d %d %d %d\n",i,p[i],W[i],dis[i]);
		ULL ans=0,flag=0;
		FOR(i,1,n){
			ans+=W[i]*dis[i];
			if (dis[i]==Inf){flag=true;break;}
		}
		if(flag)printf("No Answer\n");else printf("%I64u\n",ans);
	}
	return 0;
}