[수정 예정] nyoj 38 최소 생성 트리

package nyoj;



import java.util.Scanner;



public class Main {

    public static void main(String args[])

    {

        //System.out.println(Integer.MAX_VALUE);

        Scanner scn=new Scanner(System.in);

        int len=scn.nextInt();

        while(len-->0)

        {

            int v=scn.nextInt();

            int e=scn.nextInt();

            boolean visit[]=new boolean[v+1];//      

            int map[][]=new int[v+1][v+1];//        

            int low[]=new int[v+1];

            //  map

            //         

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

            {

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

                {

                    map[i][j]=Integer.MAX_VALUE;

                    if(i==j)map[i][i]=0;

                }

            }

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

            {

                int x=scn.nextInt();

                int y=scn.nextInt();

                map[x][y]=map[y][x]=scn.nextInt();

                

                

            }

            int ans=prime(map,v,e);

            System.out.println(ans);

            int start=scn.nextInt();

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

            {

                int tem=scn.nextInt();

                if(tem<start)start=tem;

                

            }

            

            

            //System.out.println(ans+start);

            

            

            

            

        }

        

        

        

        

    }



    private static int  prime(int[][] map,int v,int e) {

        // TODO Auto-generated method stub

        boolean visit[]=new boolean[v+1];//      

        int low[]=new int[v+1];

        visit[1]=true;

        int ans=0;

        //   low,         

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

        {

            

            if(!visit[i])

            {

                low[i]=map[1][i];

                

            }    

        }

        //     ，     ,  v-1 

        for(int i=2;i<=v;i++)

        {

            //          low  

            int k = 0;

            

            int min=1<<31-1;

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

            {

                if(!visit[j]&&low[j]<min) min=low[k=j];

                

                

            }

            ans+=min;//      

            //  k   

            visit[k]=true;

            //   k    

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

            {

                if(!visit[i]&&map[k][i]<low[i])

                {

                    low[i]=map[k][i];

                }

                

            }

            

            

            

            

        }

        

        

        return ans;

        

    }



}