#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef __int64  LL;
#define MAXN 50005
#define MAXM 50005
int val[MAXN];
struct edge{
	int v, w, nxt;
}e[MAXM<<1];
int head[MAXN],pos;
inline void add(int u, int v, int w){
	e[pos].v = v;
	e[pos].w = w;
	e[pos].nxt = head[u];
	head[u] = pos++;
}
int cnt[MAXN];
LL dist[MAXN];
bool vis[MAXN];
bool relax(int u, int v, int c){
	if (dist[u] == -1)return false;
	if (dist[v] == -1|| dist[v] > dist[u] + c){
		dist[v] = dist[u] + c;
		return true;
	}
	return false;
}
class Queue{
public:
	Queue(){
		head = tail = new Q;
	}
	void push(int x);
	int pop();
	bool empty();
private:
	struct Q{
		int val;
		Q *next;
	};
	Q *head, *tail,*front;
};
void Queue::push(int x){
	front = tail;
	tail = new Q;
	tail->val = x;
	front->next = tail;
	vis[x] = true;
	++cnt[x];
}
bool Queue::empty(){
	return head==tail;
}
int Queue::pop(){	
	front = head;
	head = head->next;
	delete front;
	return vis[head->val]=false,head->val;
}
bool Spfa(int src, int n){
	memset(cnt, 0, sizeof(cnt));
	memset(vis, false, sizeof(vis));
	memset(dist, -1,sizeof(dist));
	dist[src] = 0;
	Queue Q;
	Q.push(src);
	while (!Q.empty()){
		int u = Q.pop();
		for (int i = head[u]; ~i; i = e[i].nxt){
			int v = e[i].v;int w = e[i].w;
			if (relax(u, v, w) && !vis[v]){
				Q.push(v);
				if (cnt[v] > n)return false;//负权路
			}
		}
	}
	return true;
}
LL solve(int n){
	if(!Spfa(1, n))return -1;
	LL res = 0;
	for (int i = 1; i <= n; i++){
		if (dist[i] == -1)return -1;
		res += val[i] * dist[i];
	}
	return res;
}
int main(){
	int T;
	scanf("%d", &T);
	while (T--){
		memset(val, 0, sizeof(val));
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++){
			scanf("%d", &val[i]);
		}

		memset(head, -1, sizeof(head));
		pos = 0;
		for (int i = 1; i <= m; i++){
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			add(u, v, w);
			add(v, u, w);
		}		
		if (m == 0 || n == 0){
			printf("0\n");
			continue;
		}
		LL ans=solve(n);
		if (ans == -1)cout << "No Answer" << endl;
		else cout << ans << endl;
	}
}