Explosive Magic Circle Connection

In this problem, there are n explosive magic circles placed on the ground. The i-th magic circle has its center at \( (x_i, y_i) \) with radius \( r_i \). Two magic circles "intersect" if the distance between their centers is no more than the sum of their radii. That is, circles \(i\) and \(j\) intersect when
\[ d_{ij} \le r_i + r_j, \]
where \(d_{ij} = \sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\). If two circles do not intersect, a magical circuit (road) can be laid between their boundaries with length equal to \(\max\{0, d_{ij} - (r_i + r_j)\}\). The circles connected directly or indirectly by intersections or magical circuits will explode simultaneously.

Your task is to compute the minimum total length of magical circuits needed so that all the magic circles are connected (i.e. the entire set is connected by some combination of intersections and circuits).

Note: You must use LaTeX format for any mathematical formulas.

inputFormat

The first line of input contains an integer \(n\) (\(1 \le n \le 10^3\)), the number of magic circles. Each of the following \(n\) lines contains three numbers \(x_i\), \(y_i\), and \(r_i\) (\(-10^4 \le x_i, y_i \le 10^4\), \(0 \le r_i \le 10^4\)), representing the center coordinates and radius of the \(i\)-th magic circle.

outputFormat

Output a single number, which is the minimum total length of magical circuits needed. The answer should be printed with 6 decimal places.

sample

1
0 0 1

0.000000