Problem Description

The Space Empire wants to connect its $N$ planets by building tunnels.

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

Now you need to build $N - 1$ tunnels so that all planets are connected directly or indirectly. Find the minimum total cost required to complete 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.

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

Hint

Constraints

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

Hints and Notes

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

The score for this problem follows the original COCI settings, with a full score of $100$.

Translated by ChatGPT 5