//poj 3013 Big Christmas Tree
#include<iostream>
#include<deque>
using namespace std;
#define maxn 50002
const __int64 inf=(__int64)1<<63-1;
struct Edge
{
int v;
int weight;
int next;
}Vertex[4*maxn];
int head[maxn],curr;
int cases,v,e,i,j,edge[maxn][3],w[maxn];
void add_edge(int s,int t,int w) //新增結點不用申請空間, 跑了 579 MS
{
Vertex[curr].v=t;
Vertex[curr].weight=w;
Vertex[curr].next=head[s];
head[s]=curr++;
}
bool S[maxn];
__int64 distD[maxn],sum;
void spfa(int u)
{
fill(distD,distD+v+1,inf);
distD[u]=0;
memset(S,0,sizeof(S[0])*(v+1));
S[u]=1;
deque<int> col;
col.push_back(u);
while(!col.empty())
{
int uu=col.front();
col.pop_front();
S[uu]=0;
for(i=head[uu];i!=-1;i=Vertex[i].next)
{
if(distD[uu]+Vertex[i].weight<distD[Vertex[i].v])
{
distD[Vertex[i].v]=distD[uu]+Vertex[i].weight;
if(!S[Vertex[i].v])
{
S[Vertex[i].v]=1;
col.push_back(Vertex[i].v);
}
}
}
}
for(i=1;i<=v;++i)
if(distD[i]==inf)
{
printf("No Answer\n");
return ;
}
sum=0;
for(i=1;i<=v;++i)
sum+=w[i]*distD[i];
printf("%I64d\n",sum);
}
int main()
{
scanf("%d",&cases);
while(cases--)
{
scanf("%d%d",&v,&e);
for(i=1;i<=v;++i)
scanf("%d",&w[i]);
memset(head,-1,sizeof(head));
curr=0;
for(i=1;i<=e;++i)
{
scanf("%d%d%d",&edge[i][0],&edge[i][1],&edge[i][2]);
add_edge(edge[i][0],edge[i][1],edge[i][2]);
add_edge(edge[i][1],edge[i][0],edge[i][2]);
}
spfa(1);
}
return 0;
}
/*
這題要有個重要的轉化；
price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).
每條邊的代價為該邊所有"後繼"節點權值(重量weight)之和乘以該邊的權值(unit price)。
換個角度就是每個節點的代價為該節點到根節點的所有邊的權值乘以該節點的權值。
要使得總的花費最小,其實就是求從根結點到每個點的最短路徑*該點的權值，然後求和
資料量很大,采用SPFA算法
*/
