BOJ 2887

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100001

struct node{
    int x,y,z,num;
};
bool comp_x(node& a, node& b){
    return a.x < b.x;
}
bool comp_y(node& a, node& b){
    return a.y < b.y;
}
bool comp_z(node& a, node& b){
    return a.z < b.z;
}
struct info{
    int u,v,d;
    bool operator < (const info& a)const{
        return d < a.d;
    }
};
int ans;
vector<node> vt;
vector<info> adj;
int parent[MAXN];
int N;
int find(int x){
    if (parent[x]<0) return x;
    return parent[x] = find(parent[x]);
}
void merge(int a, int b, int d){
    a = find(a);
    b = find(b);
    if (a != b){
        parent[a] = b;
        ans+=d;
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(parent,-1,sizeof(parent));
    cin >> N;
    for (int i = 1; i <=N; i++){
        int x,y,z;
        cin >> x >> y >> z;
        vt.push_back({x,y,z,i});
    }
    sort(vt.begin(),vt.end(),comp_x);
    for (int i =0 ; i<  N-1; i++){
        int d = abs(vt[i].x-vt[i+1].x);
        adj.push_back({vt[i].num,vt[i+1].num,d}) ;
    }
    sort(vt.begin(),vt.end(),comp_y);
    for (int i =0 ; i<  N-1; i++){
        int d = abs(vt[i].y-vt[i+1].y);
        adj.push_back({vt[i].num,vt[i+1].num,d}) ;
    }
    sort(vt.begin(),vt.end(),comp_z);
    for (int i =0 ; i<  N-1; i++){
        int d = abs(vt[i].z-vt[i+1].z);
        adj.push_back({vt[i].num,vt[i+1].num,d}) ;
    }
    sort(adj.begin(),adj.end());
    for (int i = 0; i < adj.size(); i++){
        int u = adj[i].u;
        int v = adj[i].v;
        int d = adj[i].d;
        merge(u,v,d);
    }
    cout << ans <<"\n";
    return 0;
}