Problem E
Communications Satellite

Illustration of the sample input solution (beams in blue).

The Johnson Space Center has hired you to design NASA’s new communications satellite! The satellite, consisting of a set of dish antennas held together with titanium beams, must meet NASA’s exacting specifications, but a lot of the design is up to you.

Specifically, the design can be represented by a set of circles of various radii (representing the dish antennas) and line segments (the beams) in the 2D plane. A valid satellite design must meet all of the following criteria:

• The necessary size and location of each dish on the $xy$ plane was computed by NASA, and you are not allowed to reposition any of the dishes.

• You may add any number of titanium beams to the design, connecting one point on the circumference of one dish antenna to another point on the circumference of a different dish. Treat each beam as a straight line segment (of negligible width).

• Beams are not allowed to cross each other, or attach to each other. Beams are also not allowed to occlude (cover up) any part of the interior of any dish antenna.

• Your final design must consist of a single connected structure.

• Two dishes might exactly touch (in which case they are already connected to each other); but NASA guarantees that no two dish antennas overlap.

Titanium isn’t cheap these days, so you want to compute the cheapest possible compliant design: the one that minimizes the sum of the beam lengths.

Input

The first line of the input contains a single integer $1 \leq N \leq 2\, 000$, the number of dish antennas attached to the satellite.

Then follow $N$ lines, each of which contains three integers $X$, $Y$, and $R$ specifying the location and radius of one dish antenna. These integers satisfy the bounds $-1\, 000 \leq X, Y\leq 1\, 000$ and $1\leq R \leq 100$.

Output

Compute the satellite design that minimizes the sum of beam lengths, while obeying the above specifications, and print that sum. The answer is considered correct if the absolute or relative error is less than $10^{-6}$.

4
3 4 3
0 0 2
4 -2 2
9 4 1

2.47213595