Robot Challenge

You have entered a robot in a Robot Challenge. A course is set up in a $100\text{m} \times 100\text{m}$ space. Certain points in the space are designated as targets, and they are ordered — there is a target 1, a target 2, and so on. Your robot must start at $(0,0)$. From there it should go to target 1, stop for 1 second, go to target 2, stop for 1 second, and so on. It must finally reach, and stop for 1 second on, $(100,100)$.

Every target except $(0,0)$ and $(100,100)$ has a time penalty for missing it. So if your robot went straight from target 1 to target 3, skipping target 2, it would incur target 2's penalty. Note that once it reaches target 3 it cannot go back to target 2; it must hit the targets in order. Because your robot stops for 1 second on each target point, it is in no danger of hitting a target accidentally too soon. For example, if target point 3 lies directly on the line between target points 1 and 2, your robot can go straight from 1 to 2, passing over 3 without stopping. Since it did not stop, the judges will not mistakenly think it hit target 3 too soon, so they will not assess target 2's penalty. Your final score is the time (in seconds) your robot takes to reach $(100,100)$, completing the course, plus all penalties. Smaller scores are better.

Your robot is very maneuverable but a bit slow. It moves at $1\text{ m/s}$ but can turn very quickly. During the 1 second it stops on a target point, it can easily turn to face the next target point, so it can always move in a straight line between target points.

Because your robot is a bit slow, it may be advantageous to skip some targets and incur their penalty rather than actually maneuvering to them. Given a description of a course, determine your robot's best (lowest) possible score.

The input contains several test cases. Each test case begins with a line containing one integer $N$ $(1 \le N \le 1000)$, the number of targets on the course. Each of the next $N$ lines describes a target with three integers $X$, $Y$, and $P$, where $(X,Y)$ is a location on the course $(1 \le X, Y \le 99$, in meters$)$ and $P$ is the penalty incurred if the robot misses that target $(1 \le P \le 100)$. The targets are given in order — the first line after $N$ is target 1, the next is target 2, and so on. All targets on a given course are unique — there is at most one target point at any location on the course. The end of input is marked by a line containing a single $0$.

For each test case, output a single decimal number: the smallest possible score for that course. Output this number rounded (NOT truncated) to three decimal places. Print each answer on its own line, and do not print any blank lines between answers.