Problem E
Rebel Portals

https://www.kisspng.com, Used with permission

Sector quadrant MAPS-2019 has been the home of the Rebel Alliance ever since the beginning of the space war against the Galactic Empire. Now news has reached the Rebel Council that the Empire is conspiring to attack the Rebel planets in the quadrant. Unfortunately, existing communication technology does not enable a distress signal to reach all the planets in time to warn them of the upcoming invasion. Catherine has been appointed by the Council to pilot her spaceship to each Rebel planet and deliver the warning, and then return to her home planet.

Luckily for Catherine, the Rebel Alliance has been making progress towards developing portal technology that allows instant transportation between any two planets! Every Rebel planet is equipped with exactly one portal in case of an emergency such as this one. A spaceship that enters the portal on one planet immediately exits the portal on another planet (whichever planet the pilot chooses). However, there is still one glitch the Rebel scientists have not yet figured out: either entering or exiting a portal causes it to collapse on itself, so each portal can only be used once.

A planet is small enough relative to the size of the galaxy that it can be represented as a single point in 3D space. The distance between any two planets is measured as the Euclidean distance between their representative points. To move from a planet $A$ to another planet $B$, Catherine has two choices: she can fly her spaceship in the usual way, travelling the Euclidean distance between $A$ and $B$, or she can enter the portal on $A$ and exit the portal on $B$ (assuming both portals still exist), which counts as a distance of $0$. Given the position of each planet, and the fact that each portal can only be used once, can you help Catherine plan her journey to deliver the warning to each Rebel planet and return to her home planet while travelling the shortest distance possible? Note that Catherine is allowed to revisit planets.

Input

The first line of input contains an integer $n$ $(2 \leq n \leq 18)$, the number of Rebel planets. This is followed by $n$ lines, each giving the position of one Rebel planet in 3D space, the first of which is Catherine’s home planet (where she begins her mission). Every planet position is a unique triplet of space-separated integers $x$ $y$ $z$ $(0 \leq x, y, z \leq 500)$.

Output

Output a single line containing the minimum total distance Catherine needs to travel in order to visit every Rebel planet and return to her home planet. Your answer will be accepted if it is within $10^{-6}$ of the official answer.

4
0 0 1
0 1 1
2 0 3
2 1 3

2.0

6
0 0 0
50 0 0
0 50 0
50 50 0
24 24 0
24 26 0

102.0