Problem Description

The Space Empire plans to connect its $N$ planets by constructing tunnels.

Each planet is represented by a three-dimensional coordinate $(x_i, y_i, z_i)$, and the cost to build a tunnel between two planets $A$ and $B$ is $\min\{|x_A - x_B|, |y_A - y_B|, |z_A - z_B|\}$.

It is required to build $N-1$ tunnels such that all planets are directly or indirectly connected. Find the minimum total cost to accomplish this task.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain three integers $x_i, y_i, z_i$, representing the coordinates of the $i$-th planet.

It is guaranteed that no two planets have the same coordinates.

Output Format

Output the minimum total cost required.

Sample Input and Output

Sample Input #1

2
1 5 10
7 8 2

Sample Output #1

3

Sample Input #2

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

Sample Output #2

11

Sample Input #3

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

Sample Output #3

4

Notes

[Data Range and Constraints]

• For $100\%$ of the data, $1 \le N \le 10^5$, $-10^9 \le x_i, y_i, z_i \le 10^9$.

[Translation and Original Problem]

This problem is translated from COCI 2009-2010 CONTEST #7 Task 4 SVEMIR.

This problem is scored according to the original COCI settings, with a maximum score of $100$.

见题面 Input 部分

见题面 Output 部分