Svemir

Το Fourth Great and Bountiful Human Empire αναπτύσσει ένα δίκτυο σήραγγας διέλευσης που συνδέει όλους τους πλανήτες της. Η Αυτοκρατορία (Empire) αποτελείται από ~N~ πλανήτες, που αντιπροσωπεύονται ως σημεία στον τρισδιάστατο χώρο. Το κόστος του σχηματισμού μιας σήραγγας διέλευσης μεταξύ των πλανητών ~A~ και ~B~ είναι:

~TunnelCost[A,\,B]\;=\;min\{|x_A\,-\,x_B|,\;|y_A\,-\,y_B|,\;|z_A\,-\,z_B|\}~

όπου ~(x_A,\;y_A, \;z_A)~ είναι οι τρισδιάστατες συντεταγμένες του πλανήτη ~A~ και ~(x_B,\;y_B,\;z_B)~ είναι συντεταγμένες του πλανήτη ~B~. Η Αυτοκρατορία χρειάζεται να κατασκευάσει ακριβώς ~N - 1~ σήραγγες για να συνδέσει πλήρως όλους τους πλανήτες, είτε με απευθείας συνδέσεις, είτε περιφερειακά. Πρέπει να καταλήξετε στο χαμηλότερο δυνατό κόστος για την επιτυχή ολοκλήρωση αυτού του έργου.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο αριθμό ~N\;(1 \le N \le 100\,000)~, τον αριθμό πλανητών.
Οι επόμενες ~N~ γραμμές περιέχουν ακριβώς 3 ακέραιους η καθεμία. Όλοι οι ακέραιοι αριθμοί είναι μεταξύ ~-10^9~ και ~10^9~ (κλειστό διάστημα). Κάθε γραμμή περιέχει τις συντεταγμένες ~x,\;y~ και ~z~ ενός πλανήτη (με τη σειρά).
Δεν υπάρχουν δύο πλανήτες που θα καταλαμβάνουν το ίδιο ακριβώς σημείο στο διάστημα.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου θα πρέπει να περιέχει το ελάχιστο κόστος διαμόρφωσης του δικτύου των σηράγγων.

Παραδείγματα

input

2
1 5 10
7 8 2

output

3

input

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

output

11

input

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

output

4