Minimum Spanning Tree Sum

Given n points in the plane with coordinates \((x_i, y_i)\) for \(i = 1, 2, \dots, n\). The weight of the edge connecting points \(i\) and \(j\) is defined as $$\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}.$$ Your task is to compute the sum of the edge weights in the Minimum Spanning Tree (MST) of these points.

inputFormat

The first line contains an integer \(n\) (\(2 \leq n\leq 1000\)), the number of points. Each of the following \(n\) lines contains two real numbers \(x_i\) and \(y_i\) representing the coordinates of the \(i\)-th point.

outputFormat

Output a single real number representing the sum of the edge weights in the MST. The answer should be printed with at least 6 decimal places.

sample

4
0 0
0 1
1 0
1 1

3.000000