You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

三维生成树

题目描述

三维空间内有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i,z_i)$ ，而对任意 $1\leq i< j\leq n$ ，第 $i$ 个点和第 $j$ 个点之间连有一条边权为 $\min\{|x_i-x_j|,|y_i-y_j|,|z_i-z_j|\}$ 的边。

求这个完全图的最小生成树。

输入格式

第一行一个整数 $n$。接下来的 $n$ 行，每行三个整数 $x_i,y_i,z_i$，表示第 $i$ 个点的坐标。

输出格式

输出最小生成树的边权和。

样例 #1

样例输入 #1

2
1 5 10
7 8 2

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

11

样例 #3

样例输入 #3

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

样例输出 #3

4

数据规模与约定

• 对 $20\%$ 的数据，$n\le 100$ ；
• 对 $40\%$ 的数据，$n\le 10^4$ ；
• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$-10^9 \le x_i,y_i,z_i \le 10^9$。