1 package 最小生成树;  2   3 import java.util.Arrays;  4 import java.util.Scanner;  5 class Node implements Comparable<Node>  6 {  7     int x;  8     int y;  9     int val; 10     public Node(int x,int y,int val) 11     { 12         this.x=x; 13         this.y=y; 14         this.val=val; 15     } 16     @Override 17     public int compareTo(Node o) { 18         return this.val-o.val; 19     } 20      21  22 } 23  24 public class Main { 25      26     public static void init(int a[])//并查集初始化，用来判断是否有环 27     { 28         for(int i=1;i<a.length;i++)a[i]=i; 29          30     } 31     public static int find(int a[],int x) //查找节点的父亲,没有优化的方法 32     { 33         while(a[x]!=x) 34         { 35             x=a[x]; 36         } 37          38         return x; 39     } 40     public static boolean union(int a[],int x,int y)//union一条边 41     { 42         int fx=find(a, x); 43         int fy=find(a, y); 44         if(fx!=fy) 45         { 46             a[fx]=fy; 47             return true;  //成功加入 48              49         } 50         return false;//成环 51          52     } 53  54     public static void main(String[] args) { 55         // TODO Auto-generated method stub 56         Scanner scn=new Scanner(System.in); 57         int len=scn.nextInt(); 58         while(len-->0) 59         { 60             int ans=0;//保存最后的答案 61             int v=scn.nextInt(); 62             int e=scn.nextInt(); 63             Node n[]=new Node[e]; 64             for(int i=0;i<e;i++) 65             { 66                 n[i]=new Node(scn.nextInt(),scn.nextInt(),scn.nextInt()); 67                  68                  69             } 70              71             Arrays.sort(n); 72             //并查集的初始化 73             int father[]=new int[v+1]; 74             init(father); 75             int index=0; 76             for(int i=0;i<e;i++) 77             { 78                 if(union(father, n[i].x,n[i].y)) 79                 { 80                      81                     index++; //没成环，加入这条边 82                     ans+=n[i].val; 83                  84                      85                 } 86                 if(index==v-1) 87                 { 88                     break; 89                 } 90                 91                  92                  93             } 94             int min=scn.nextInt(); 95              96             for(int j=1;j<v;j++) 97             { 98                 int temp=scn.nextInt(); 99                 if(min>temp) min=temp;100                 101             }102             System.out.println(ans+min);103             104         }105 106     }107 108 109 110 111 }