[COCI2009-2010#7] SVEMIR
题目描述
太空帝国要通过建造隧道来联通它的 $N$ 个星球。
每个星球用三维坐标 $(x_i,y_i,z_i)$ 来表示，而在两个星球 $A,B$ 之间建造隧道的价格为 $\min\{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|\}$。
现要建造 $N-1$ 条隧道使得所有的星球都能直接或间接相连。求完成该任务所需的最小总价。
输入输出格式
输入格式
第一行，一个整数 $N$。
接下来的 $N$ 行，每行三个整数 $x_i,y_i,z_i$，表示第 $i$ 个星球的坐标。
数据保证不存在两个具有相同坐标的星球。
输出格式
输出所需的最小总价。
输入输出样例
输入样例 #1
2
1 5 10
7 8 2输出样例 #1
3输入样例 #2
3
-1 -1 -1
5 5 5
10 10 10输出样例 #2
11输入样例 #3
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19输出样例 #3
4说明
**【数据规模与约定】**
- 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$-10^9 \le x_i,y_i,z_i \le 10^9$。
**【提示与说明】**
**题目译自 [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 4 SVEMIR_。**
**本题分值按 COCI 原题设置，满分 $100$。**