407203: GYM102697 174 Interstellar Travel

You're traveling through space, but unfortunately, your spaceship has a limited amount of fuel. There are $$$n$$$ planets that you want to travel to on your journey through space, and each planet can be represented by an $$$x$$$, $$$y$$$, and $$$z$$$ coordinate.

You start on Earth, which can be represented as the origin (0, 0, 0) on the 3D coordinate plane. You want to find the minimum distance you can travel, if you start on Earth, visit all of the planets at least once, and end on Earth.

Recall that to calculate the distance between two points in 3D space, you can use the distance formula:

The first line of input consists of a single positive integer $$$n$$$: the number of planets. $$$n$$$ will be less than or equal to 8.

The next $$$n$$$ lines each contain three space-separated integers: the $$$x$$$, $$$y$$$, and $$$z$$$ coordinates of each planet.

Remember that the coordinates of the Earth are (0, 0, 0).

Output a single positive integer: the minimum total distance that you travel, if you start and end on Earth, and visit all of the planets.

Don't round your answer.

4
-1 0 0
-2 0 0
2 0 0
1 0 0

8.0

8
3 3 2
-3 -3 8
6 8 7
-5 6 3
-2 7 6
-4 4 -3
1 5 -3
5 4 0

59.308719980502595

4
3 3 -2
-2 5 4
4 8 -6
8 17 -3

45.292233300341344