좌표평면에서의 최소 신장 트리를 구성하는 문제입니다. 간선이 $\begin{pmatrix} n \\ 2 \end{pmatrix}$개이기 때문에 모든 간선을 저장할 수는 없고, 후보를 추려야 합니다. 간선의 가중치가 $\min\{|\Delta x|, |\Delta y|, |\Delta z|\}$이므로 x축, y축, z축 기준으로 정렬한 다음에 인접한 정점 사이의 간선을 확인하는 방법을 떠올릴 수 있습니다. 이후는 크루스칼 알고리즘을 통해 최소 신장 트리를 구성하면 됩니다.

여기서 “축 방향으로 인접한 정점 외에 다른 정점이 있는 경우를 제외하였다"라는 점이 의심스럽습니다. 이때에도 최소 신장 트리가 만들어진다는 것을 증명하려면, 축 방향으로 인접한 정점만으로 구성된 최소 신장 트리가 존재한다는 것만 보이면 됩니다. 왜냐하면 크루스칼 알고리즘은 연결 그래프에서 반드시 최소 신장 트리를 찾고, 축 방향으로 인접하지 않은 정점을 잇는 간선은 존재하지 않기 때문입니다.

use std::io::{stdin, Read};
fn weight(a: (i32, i32, i32, usize), b: (i32, i32, i32, usize)) -> i32 {
    (b.0 - a.0)
        .abs()
        .min((b.1 - a.1).abs())
        .min((b.2 - a.2).abs())
}
fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
    let n = input.next().unwrap() as usize;
    let mut points = vec![];
    for i in 0..n {
        let x = input.next().unwrap();
        let y = input.next().unwrap();
        let z = input.next().unwrap();
        points.push((x, y, z, i));
    }
    points.sort_unstable();
    let mut edges = vec![];
    for window in points.windows(2) {
        let w = weight(window[0], window[1]);
        edges.push((w, window[0].3, window[1].3));
    }
    points.sort_unstable_by_key(|&(_, y, _, _)| y);
    for window in points.windows(2) {
        let w = weight(window[0], window[1]);
        edges.push((w, window[0].3, window[1].3));
    }
    points.sort_unstable_by_key(|&(_, _, z, _)| z);
    for window in points.windows(2) {
        let w = weight(window[0], window[1]);
        edges.push((w, window[0].3, window[1].3));
    }
    edges.sort_unstable();
    let mut forest = SetForest::new(n);
    let mut min = 0;
    for (w, u, v) in edges {
        let pu = forest.find(u);
        let pv = forest.find(v);
        if pu != pv {
            min += w;
            forest.merge(pu, pv);
        }
    }
    println!("{}", min);
}

struct SetForest {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl SetForest {
    fn new(s: usize) -> Self {
        Self {
            parent: (0..s).collect(),
            rank: vec![1; s],
        }
    }

    fn find(&mut self, mut i: usize) -> usize {
        while i != self.parent[i] {
            self.parent[i] = self.parent[self.parent[i]];
            i = self.parent[i];
        }
        i
    }

    fn merge(&mut self, mut pu: usize, mut pv: usize) {
        if self.rank[pu] < self.rank[pv] {
            std::mem::swap(&mut pu, &mut pv);
        }
        self.parent[pv] = pu;
        if self.rank[pu] == self.rank[pv] {
            self.rank[pu] += 1;
        }
    }
}