#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

#define ll long long 
const int MAXN = 50005;
const int MAXM = 100005;
const ll INF = ((ll)1)<<62;
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline double max(double a, double b) { return a > b ? a : b; }
inline double min(double a, double b) { return a < b ? a : b; }

int wn[MAXN], first[MAXN];
int v[MAXM], nxt[MAXM], we[MAXM];
bool inq[MAXN];
ll d[MAXN];

int main()
{
	//freopen("poj3013.in", "r", stdin);
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n, m;	
		int i, j;	
		scanf("%d%d", &n, &m);
		for(i = 1; i <= n; i++) scanf("%d", &wn[i]);
		for(i = 1; i <= n; i++) first[i] = -1;
		int cnt = 0;
		for(i = 0; i < m; i++)
		{
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			v[cnt] = b; we[cnt] = c;
			nxt[cnt] = first[a];
			first[a] = cnt++;
			v[cnt] = a; we[cnt] = c;
			nxt[cnt] = first[b];
			first[b] = cnt++;
		}
		
		for(i = 1; i <= n; i++) { d[i] = INF; inq[i] = false; }
		d[1] = 0;
		queue<int> q;
		q.push(1);
		inq[1] = true;
		while(!q.empty())
		{
			int x = q.front(); q.pop();
			inq[x] = false;
			for(int e = first[x]; e != -1; e = nxt[e]) if(d[v[e]] > d[x] + we[e])
			{
				d[v[e]] = d[x] + we[e];
				if(!inq[v[e]])
				{
					inq[v[e]] = true;
					q.push(v[e]);
				}
			}
		}
		
		bool exist = true;
		ll sum = 0;
		for(i = 2; i <= n; i++)
			if(d[i] > -1) sum += d[i]*wn[i];
			else{ exist = false; break; }
		if(exist) printf("%lld\n", sum);
		else printf("NO Answer\n");
	}
	return 0;
}