/*

//代码一：克鲁斯卡尔算法（超时）

#include<stdio.h>

#include<malloc.h>

#include<string.h>

#include<string.h>

struct edge

{

 int v1;

 int v2;

 int c;

}t;

int v,e,sum;

int find(int father[],int v)

{

 int temp=v;

 while(father[temp]>0)

  temp=father[temp];

 return temp;

}

void Kruskal(struct edge edges[],int n)

{

 int i,j,vf1,vf2;

 int father[501];

 memset(father,-1,sizeof(father));

 i=0;

 j=0;

 while(i<v&&j<e)

 {

  vf1=find(father,edges[i].v1);

  vf2=find(father,edges[i].v2);

  if(vf1!=vf2)

  {

   father[vf1]=vf2;

   ++j;

   sum+=edges[i].c;

  }

  ++i;

 }

}

int main()

{

 int n,k,i,j,min;

 struct edge *edges;

 scanf("%d",&n);

 while(n--)

 {

  sum=0;

  min=0x3fffffff;

  scanf("%d%d",&v,&e);

  edges=(struct edge*)malloc(e*sizeof(struct edge));

  for(i=0;i<e;++i)

   scanf("%d%d%d",&edges[i].v1,&edges[i].v2,&edges[i].c);

  for(i=e-1;i>=0;--i)

   for(j=0;j<i;++j)

    if(edges[j].c>edges[j+1].c)

    {

     t=edges[j];

     edges[j]=edges[j+1];

     edges[j+1]=t;

    }

  Kruskal(edges,v);

  for(i=0;i<v;++i)

  {

   scanf("%d",&k);

   if(k<min)

   {

    min=k;

   }

  }

  printf("%d\n",sum+min);

 }

 return 0;

}

*/

//代码二：普里母算法

#include<stdio.h>

#include<malloc.h>

void prim(int**map,int n);

int sum;

int main()

{

 int n,i,j,min,a,b,c,e,v;

 int **map;

 scanf("%d",&n);

 while(n--)

 {

  sum=0;

  min=0x7fffffff;

  scanf("%d%d",&v,&e);

  map=(int **)malloc((v+1)*sizeof(int*));//邻接矩阵

  for(i=0;i<=v;++i)

   map[i]=(int *)malloc((v+1)*sizeof(int));

  for(i=0 ; i<=v ;++i)

   for(j=i+1;j<=v;++j)

    map[i][j]=map[j][i]=0x7fffffff;

  for(i=0;i<e;++i)

  {

   scanf("%d%d%d",&a,&b,&c);

   map[a][b]=c;

   map[b][a]=c;

  }

  prim(map,v);

  for(i=0;i<v;++i)

  {

   scanf("%d",&a);

   if(a<min)

    min=a;

  }

  printf("%d\n",sum+min);

 }

 return 0;

}

void prim(int** map,int n)

{

    int *lowcost=(int *)malloc((n+1)*sizeof(int));

    int i,j,k,min;

    sum=0;

   lowcost[1]=0;

    for(i=2;i<=n;++i)//初始化

    lowcost[i]=map[1][i];

   for(i=2;i<=n;++i)//从第二个点开始找

   {

      min=0x3fffffff;

      for(j=2,k=2;j<=n;++j)

   {

              if(lowcost[j]<min&&lowcost[j]!=0)

              {

      min=lowcost[j];

      k=j;

     }

      }

      sum+=lowcost[k];

      lowcost[k]=0;//标记已访问

      for(j=2;j<=n;++j)

      {

    if(lowcost[j]&&lowcost[j]>map[k][j])

     lowcost[j]=map[k][j];

   }

      }

}