Attack on the Star System

In this problem, Xiao Ming pilots his spaceship to attack a star system containing \( n \) planets numbered \(1, 2, \ldots, n\). The \( i \)-th planet is located at \((x_i, y_i, z_i)\) and has a defense strength of \(w_i\).

He must determine an order \(p_1, p_2, \ldots, p_n\) to attack the planets such that the total energy required is minimized. The energy used is defined as

\[ E = \sum_{i=2}^{n} d(p_{i-1}, p_i) \times w_{p_i}, \]

where \(d(p_{i-1}, p_i)\) represents the Euclidean distance between the planets \(p_{i-1}\) and \(p_i\). Note that the energy cost when attacking the first planet is zero.

Your task is to compute the minimum energy required to attack all the planets in an optimal order.

inputFormat

The input begins with an integer \(n\) representing the number of planets. It is followed by \(n\) lines, each containing four numbers: \(x_i\), \(y_i\), \(z_i\) and \(w_i\), which represent the coordinates and the defense strength of the \(i\)-th planet.

outputFormat

Output a single number, which is the minimum energy required to attack all the planets. The answer should be printed with 10 decimal places.

sample

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

5.0000000000