题目描述

太空帝国要通过建造隧道来联通它的 $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$ 个星球的坐标。

数据保证不存在两个具有相同坐标的星球。

输出格式

输出所需的最小总价。

2
1 5 10
7 8 2

3

3
-1 -1 -1
5 5 5
10 10 10

11

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

4

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，$1 \le N \le 10^5$，$-10^9 \le x_i,y_i,z_i \le 10^9$。

【提示与说明】

题目译自 COCI 2009-2010 CONTEST #7 Task 4 SVEMIR。

本题分值按 COCI 原题设置，满分 $100$。