[백준] 21924번 도시 건설 (gold 4

import java.io.*;
import java.util.*;

class Point{
    int city;
    int v;
    public Point(int city, int v){
        this.city=city;
        this.v=v;
    }
}
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st=new StringTokenizer(br.readLine());

        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        ArrayList<Point>[] arr=new ArrayList[n+1];
        for(int i=0; i<=n; i++){
            arr[i]=new ArrayList<>();
        }
        //얼마나 절약인지 알아보는 것이므로.
        //모든 간선들의 비용을 더하고, mst값을 빼면됨
        long total=0;
        for(int i=0; i<m; i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.valueOf(st.nextToken());
            int b=Integer.valueOf(st.nextToken());
            int c=Integer.valueOf(st.nextToken());

            arr[a].add(new Point(b,c));
            arr[b].add(new Point(a,c));
            total+=c;
        }


        //mst
        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1 , Point o2){
                return o1.v-o2.v;
            }
        });

        int num=0;
        boolean[] visit=new boolean[n+1];
        boolean connected=false;
        long sum=0;

        que.offer(new Point(1,0));
        while(!que.isEmpty()){
            Point temp=que.poll();
            if(visit[temp.city]){
                continue;
            }
            sum+=temp.v;
            visit[temp.city]=true;
            num++;
            if(num==n){
                connected=true;
                break;
            }

            int end=arr[temp.city].size();
            for(int i=0; i<end; i++){
                Point p=arr[temp.city].get(i);
                if(visit[p.city]){
                    continue;
                }
                que.offer(new Point(p.city, p.v));
            }
        }

        if(!connected){
            bw.write("-1");
        }
        else {
            bw.write(total - sum + "");
        }
        bw.flush();

    }
}

//간단한 mst문제, prim의 알고리즘 이용