Description

He marked $N$ points on a topographic map, where each point $P_i$ has coordinates $(x_i, y_i, z_i)$. Among all points, the height values $z$ are pairwise distinct. HKE plans to climb from the lowest point to the highest point, and his climbing satisfies the following conditions:

(1) He visits every point he marked.

(2) Starting from the second point, the height $z$ of each visited point is higher than that of the previous point.

(3) HKE can fly. The distance he travels from a point $P_i$ to $P_j$ is the Euclidean distance between the two points, i.e., $\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2}$.

Now, HKE wants you to compute the total distance of his climb.

Input Format

The first line contains an integer $N$ indicating the number of points on the map.

Each of the next $N$ lines contains three integers $x_i, y_i, z_i$, representing the coordinates of the $i$-th point.

Output Format

Output a real number representing the total distance HKE needs to climb (rounded to three decimal places).

5
2 2 2
1 1 1
4 4 4
3 3 3
5 5 5

6.928

Hint

For 100% of the testdata, $1\leq N\leq 50000$, and the answer is within the range of a double.

Translated by ChatGPT 5