P8074 [COCI 2009/2010 #7] SVEMIR

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.

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 the minimum total cost required.

**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](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 4 SVEMIR_.** **The score for this problem follows the original COCI settings, with a full score of $100$.** Translated by ChatGPT 5