> #include <cstdio>
> 
> const long MaxN=50000;
> const long MaxM=50000;
> 
> struct node {
>   long a,m;       
> };
> 
> long T;
> 
> node heap[2*MaxM];
> long count;
> 
> long N,M;
> long min[MaxN],head[MaxN],minpoint;
> long point[MaxM*2],next[MaxM*2],dis[MaxM*2];
> 
> long cost[MaxN],weight[MaxN];
> __int64 ans;
> bool noanswer;
> 
> void Open() {
>   freopen ("3013.in","r",stdin);
>   freopen ("3013.out","w",stdout);     
> } 
> 
> void Close() {
>   fclose(stdin);
>   fclose(stdout);     
> }
> 
> inline void swap(long a,long b) {
>   node temp;
>   temp=heap[a]; heap[a]=heap[b]; heap[b]=temp;
> }
> 
> inline long Min(long a,long b) {
>   if (heap[a].a<heap[b].a) return a;
>   return b;
> }
> 
> void Up(long k) {
>   long f,t;
>   f=(k-1)/2;
>   while (k!=0) {
>     t=Min(f,k);
>     if (t==f) break;
>     swap(k,f); k=f;
>   }
> }
> 
> void Down(long k) {
>   long l,r,t;
>   while (1) {
>     l=k*2+1; r=k*2+2;
>     if (l>=count) break;
>     if (r>=count) t=Min(k,l); else t=Min(k,Min(l,r));
>     if (t==k) break;
>     swap(k,t); k=t;
>   }
> }
> 
> void Dijkstra_Heap() {
>   long i,j; minpoint=0;
>   for (i=0;i<N;i++) min[i]=-1; min[0]=0;
>   count=0; i=0;
>   while (min[minpoint]>=0&&i<=N) {
>     j=head[minpoint];
>     while (j!=-1) {
>       if (min[minpoint]+dis[j]<min[point[j]]||min[point[j]]==-1) {
>         min[point[j]]=min[minpoint]+dis[j];
>         heap[count].a=min[point[j]]; heap[count].m=point[j]; count++;
>         Up(count-1);
>       } j=next[j];
>     }
>     cost[minpoint]=min[minpoint];
>     min[minpoint]=-2; minpoint=heap[0].m;
>     while (min[minpoint]==-2&&count>0) {
>       heap[0]=heap[--count]; Down(0);
>       minpoint=heap[0].m;
>     }
>     i++;
>   }
> }
> 
> void init() {
>   long i,a,b,c,tcount=0;
>   scanf ("%ld%ld",&N,&M);
>   for (i=0;i<N;i++) head[i]=-1;
>   for (i=0;i<2*M;i++) next[i]=-1;
>   count=0; ans=0; noanswer=false;
>   for (i=0;i<N;i++) scanf ("%ld",&weight[i]);
>   for (i=0;i<M;i++) {
>     scanf ("%ld%ld%ld",&a,&b,&c); a--; b--;
>     if (a==b) continue;
>     point[tcount]=b; next[tcount]=head[a]; dis[tcount]=c; head[a]=tcount++;
>     point[tcount]=a; next[tcount]=head[b]; dis[tcount]=c; head[b]=tcount++;
>   }
> }
> 
> void work() {
>   long i; __int64 a,b,c;
>   for (i=0;i<N;i++) cost[i]=-1;
>   Dijkstra_Heap();
>   for (i=0;i<N;i++) if (cost[i]==-1) {noanswer=true; return;}
>   for (i=0;i<N;i++) {
>     a=cost[i]; b=weight[i]; c=a*b;
>     ans+=c;
>   }
> }
> 
> void output() {
>   if (noanswer) printf ("No Answer\n");
>   else printf ("%I64d\n",ans);
> }
> 
> int main() {
> //  Open();
>   scanf ("%ld",&T);
>   for (;T>0;T--) {
>     init();
>     work();
>     output();    
>   }
> //  Close();
>   return 0;
> }