1234 | Imperiul Galactic

Imperiul Galactic a trebuit sa renunțe la bine-cunoscutele nave spațiale, din cauza normelor tot mai ridicate de poluare. Administrația este nevoită să dezvolte o rețea de tuneluri transplanetare prin care vor circula locuitorii.
Imperiul este format din $N$ planete, reprezentate ca puncte în spațiu. Costul formării unui tunel transplanetar între două planete $A$ și $B$ este:
$TunnelCost[A, B] = min(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)$, unde $(x_A, y_A, z_A)$ sunt coordonatele 3D ale planetei $A$ si $(x_B, y_B, z_B)$ sunt coordonatele 3D ale planetei $B$.

Cerință

Imperiul trebuie să construiască exact $N-1$ tuneluri pentru a conecta complet toate planetele între ele. Din cauza rebelilor, administrația Imperiului Galactic nu mai are așa de mulți bani ca pe vremuri și trebuie să îi folosească cât mai eficient. Gasiți cel mai mic cost posibil pentru finalizarea cu succes a acestui proiect.

Notă: Planetele ocupă locuri distincte in spațiu.

Date de intrare

Prima linie de intrare conține numărul natural $N$, numărul de planete.
Urmatoarele $N$ linii conțin fiecare câte un triplet de valori întregi $x_k \ y_k \ z_k$, reprezentând coordonatele planetelor.

Date de ieșire

Afișați pe prima linie costul minim al rețelei de tuneluri.

Restricții și precizări

• $1 \le N \le 10^5$.
• $-10^9 \le x_k, y_k, z_k \le 10^9$.
• Pentru teste în valoare de 50 de puncte, $N \le 1000$.

Exemplu 1

stdin

2
1 5 10
7 8 2

stdout

3

Exemplu 2

stdin

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

stdout

11

Exemplu 3

stdin

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

stdout

4