Space Empire Tunnel Construction

The Space Empire wants to connect its N planets by building tunnels. Each planet is represented by three-dimensional coordinates \( (x_i, y_i, z_i) \), and the cost to build a tunnel between two planets \(A\) and \(B\) is given by \(\min\{|x_A-x_B|,\;|y_A-y_B|,\;|z_A-z_B|\}\). The task is to build exactly \(N-1\) tunnels such that all planets are connected either directly or indirectly. Compute the minimum total cost needed to complete this task.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(N\) \((2 \leq N \leq 10^5)\) representing the number of planets.
Each of the following \(N\) lines contains three integers \(x_i, y_i, z_i\) \((-10^9 \leq x_i, y_i, z_i \leq 10^9)\) corresponding to the coordinates of the \(i\)-th planet.

outputFormat

Output a single integer representing the minimum total cost to connect all the planets.

sample

3
1 2 3
2 3 4
3 1 5

2