#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

typedef unsigned __int64 lint;
const int N=500005;
const lint inf=20000000000;

struct edge
{
	int to,v,next;
}mp[2*N];

int p[N],q[N+2];
lint dis[N],a[N];
bool u[N];

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m,i,j,x,y,z;
		scanf("%d%d",&n,&m);
		if(n==0)
		{
			while(m--)scanf("%d%d%d",&x,&y,&z);
			printf("0\n");
			continue;
		}
		if(n==1)
		{
			scanf("%d",&x);
			while(m--)scanf("%d%d%d",&x,&y,&z);
			printf("0\n");
			continue;
		}
		for(i=1;i<=n;i++)scanf("%I64u",&a[i]);
		memset(p,-1,sizeof(p));
		for(i=0,j=0;i<m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			mp[j].to=y,mp[j].v=z,mp[j].next=p[x],p[x]=j++;
			mp[j].to=x,mp[j].v=z,mp[j].next=p[y],p[y]=j++;
		}
		for(i=0;i<=n;i++)
		{
			u[i]=0;
			dis[i]=inf;
		}
		memset(dis,-1,sizeof(dis));
		dis[1]=0;
		int head=0,tail=1;
		q[0]=1;
		while(head!=tail)
		{
			int t=q[head];
			head=(head+1)%N;
			u[t]=0;
			for(i=p[t];i!=-1;i=mp[i].next)
			{
				int tt=mp[i].to,v=mp[i].v;
				if(dis[tt]==-1||dis[tt]>dis[t]+v)
				{
					dis[tt]=dis[t]+v;
					if(u[tt]==0)
					{
						u[tt]=1;
						q[tail]=tt;
						tail=(tail+1)%N;
					}
				}
			}
		}
	    lint ans=0;
		bool flag=0;
		for(i=1;i<=n;i++)
		{
			if(dis[n]==-1)
			{
				flag=1;
				break;
			}
			ans+=(dis[i]*a[i]);
		}
		if(flag)printf("No Answer\n");
		else printf("%I64u\n",ans);
	}
	return 0;
}