#include <stdio.h>
#include <string.h>
#define MAXN 51001
#define NIL 922337203685477580

typedef long long IIL;
struct _Node
{
	int v, next, w;
}edge[2*MAXN+100];
int queue[MAXN+100], visit[MAXN], g[MAXN], weight[MAXN];
IIL dist[MAXN];
int v, e, p;

void SPFA( int s, int N )
{
	int h, t, x, i, tt, vv;
	IIL *temp = dist;
	for ( i = 0; i <= N; ++i )
		*temp++ = NIL;
	memset( visit, 0, sizeof( visit ) );
	dist[s] = 0;
	h = 0; t = 1;
	queue[0] = s; visit[s] = 1;
	while ( h != t )
	{
		x = queue[h]; visit[x] = 0;
		for ( i = g[x]; i != -1; i = edge[i].next )
		{
			tt = edge[i].w; vv = edge[i].v;
			if ( dist[vv] - tt > dist[x] )
			{
				dist[vv] = dist[x] + tt;
				if ( !visit[vv] )
				{
					queue[t] = vv; visit[vv] = 1;
					if ( ++t >= N ) t = 0;
				}
			}
		}
		if ( ++h >= N ) h = 0;
	}
}

void addEdge( int u, int v, int w )
{
	edge[p].next = g[u];
	edge[p].v = v; edge[p].w = w;
	g[u] = p++;
}

int GetInt()
{
	char ch;
	int t = 0;
	while ( ( ch = getchar() ) != EOF )
	{
		if ( ch >= '0' && ch <= '9' ) break;
	}
	do
	{
		if ( ch < '0' || ch > '9' ) return t;
		t = ( t << 3 ) + ( t << 1 ) + ch - '0';
	}while ( ( ch = getchar() ) != EOF );
}

int main()
{
	int cases, i, uu, vv, ww;
	IIL ans;

	//scanf( "%d", &cases );
	cases = GetInt();
	while ( cases-- )
	{
		memset( g, -1, sizeof( g ) );
		//scanf( "%d%d", &v, &e );
		v = GetInt(); e = GetInt();
		for ( i = 0; i < v; ++i )
			weight[i] = GetInt();
			//scanf( "%d", &weight[i] );
		for ( p = i = 0; i < e; ++i )
		{
			//scanf( "%d%d%d", &uu, &vv, &ww );
			uu = GetInt(); vv = GetInt(); ww = GetInt();
			addEdge( uu-1, vv-1, ww );
			addEdge( vv-1, uu-1, ww );
		}
		if ( v == 0 || v == 1 )
		{
			printf( "0\n" );
			continue;
		}
		SPFA( 0, v );
		for ( ans = 0, i = 0; i < v; ++i )
		{
			if ( dist[i] == NIL ) break;
			ans += dist[i]*weight[i];
		}
		if ( i == v )
			printf( "%lld\n", ans );
		else
			printf( "No Answer\n" );
	}
	return 0;
}