[백준] 1717번 집합의 표현 (gold 5

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

class Point{
    int n;
    int v;
    public Point(int n,int v){
        this.n=n;
        this.v=v;
    }
}

class Node{
    int n1;
    int n2;
    int v;
    public Node(int n1, int n2, int v){
        this.n1=n1;
        this.n2=n2;
        this.v=v;
    }
}
public class Main{
    static int[] num;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int t=Integer.valueOf(br.readLine());

        PriorityQueue<Point> qx=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });
        PriorityQueue<Point> qy=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });
        PriorityQueue<Point> qz=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });
        PriorityQueue<Node> que=new PriorityQueue<>(new Comparator<Node>(){
            public int compare(Node o1, Node o2){
                return o1.v-o2.v;
            }
        });

        StringTokenizer st;
        for(int i=1; i<=t; i++){
            st=new StringTokenizer(br.readLine());
            int x=Integer.valueOf(st.nextToken());
            int y=Integer.valueOf(st.nextToken());
            int z=Integer.valueOf(st.nextToken());

            qx.offer(new Point(i,x));
            qy.offer(new Point(i,y));
            qz.offer(new Point(i,z));
        }

        int tv=0;
        int tn=0;

        Point p=qx.poll();
        tv=p.v;
        tn=p.n;
        while(!qx.isEmpty()){
            p=qx.poll();
            que.offer(new Node(tn, p.n, Math.abs(tv-p.v)));
            tv=p.v;
            tn=p.n;
        }

        p=qy.poll();
        tv=p.v;
        tn=p.n;
        while(!qy.isEmpty()){
            p=qy.poll();
            que.offer(new Node(tn, p.n, Math.abs(tv-p.v)));
            tv=p.v;
            tn=p.n;
        }

        p=qz.poll();
        tv=p.v;
        tn=p.n;
        while(!qz.isEmpty()){
            p=qz.poll();
            que.offer(new Node(tn, p.n, Math.abs(tv-p.v)));
            tv=p.v;
            tn=p.n;
        }

        long answer=0;
        int planet=0;
        num=new int[t+1];
        for(int i=1; i<=t; i++){
            num[i]=i;
        }

        if(que.size()==0){
            System.out.println(0);
        }
        else{
            while(!que.isEmpty()){
                Node temp=que.poll();
                if(Find(temp.n1) == Find(temp.n2)){
                    continue;
                }
                Union(temp.n1,temp.n2);
                answer+=temp.v;
                planet++;
                if(planet==t-1){
                    break;
                }
            }
            bw.write(answer+"");
            bw.flush();
        }
    }
    public static int Find(int a){
        if(a==num[a]){
            return a;
        }
        else return num[a]=Find(num[a]);
    }

    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb){
            num[fa]=fb;
        }
    }

}