因为王记更新反向距离了搞了一次WA。。。
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

double dist[1010][1010];

double d(int x1, int y1, int x2, int y2){
	return sqrt(0.0 + (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

inline double mn(double a, double b){
	return (a<b) ? a : b;
}

inline double mx(double a, double b){
	return (a>b) ? a : b;
}

void swp(int &i1, int &i2){
	int temp = i1;
	i1 = i2;
	i2 = temp;
}

const double infty = 100000000.0;

int main() {
	int N;
	while(1){
		scanf("%d", &N);
		if(N == 0) break;
		int x[1010], y[1010], l[1010];
		scanf("%d%d%d", &x[1], &y[1], &l[1]);
		scanf("%d%d%d", &x[N], &y[N], &l[N]);
		for(int i = 2; i < N; i++){
			scanf("%d%d%d", &x[i], &y[i], &l[i]);
		}
		for(int i = 1; i < N; i++){
			for(int j = i+1; j <= N; j++){
				int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
				int x3,y3,x4,y4;
				if(l[i]>=0){
					x3 = x1+l[i], y3 = y1;
				}
				else{
					x3 = x1, y3 = y1-l[i];
				}
				if(l[j]>=0){
					x4 = x2+l[j], y4 = y2;
				}
				else{
					x4 = x2, y4 = y2-l[j];
				}
				if(l[i]>=0 && l[j]>=0){
					//都是东西的
					if(x3>=x2 && x4>=x1){
						dist[i][j] = abs(0.0+y1-y2);
					}
					else if(x2>x3){
						dist[i][j] = sqrt(0.0+(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
					}
					else{
						dist[i][j] = sqrt(0.0+(x1-x4)*(x1-x4)+(y1-y4)*(y1-y4));
					}
				}
				else if(l[i]<0 && l[j]<0){
					//都是南北的
					if(y3>=y2 && y4>=y1){
						dist[i][j] = abs(0.0+x1-x2);
					}
					else if(y2>y3){
						dist[i][j] = sqrt(0.0+(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
					}
					else{
						dist[i][j] = sqrt(0.0+(x1-x4)*(x1-x4)+(y1-y4)*(y1-y4));
					}
				}
				else{
					if(l[i]<0 && l[j]>=0){
						swp(x1,x2), swp(y1,y2), swp(x3,x4), swp(y3,y4);
					}
					if(x1<=x2 && x2<=x3 && y2<=y1 && y1<=y4){
						dist[i][j] = 0;
					}
					else if(x1<=x2 && x2<=x3 && y1>y4){
						dist[i][j] = y1-y4;
					}
					else if(x1<=x2 && x2<=x3 && y1<y2){
						dist[i][j] = y2-y1;
					}
					else if(y2<=y1 && y1<=y4 && x2>x3){
						dist[i][j] = x2-x3;
					}
					else if(y2<=y1 && y1<=y4 && x2<x1){
						dist[i][j] = x1-x2;
					}
					else if(x2<x1 && y1<y2){
						dist[i][j] = d(x1,y1,x2,y2);
					}
					else if(x2>x3 && y1<y2){
						dist[i][j] = d(x2,y2,x3,y3);
					}
					else if(x2<x1 && y1>y4){
						dist[i][j] = d(x1,y1,x4,y4);
					}
					else{
						dist[i][j] = d(x3,y3,x4,y4);
					}
				}
				dist[j][i] = dist[i][j];
			}
		}
		double estm[1010];
		estm[1] = 0;
		for(int i = 2; i <= N; i++) estm[i] = dist[1][i];
		bool used[1010] = {0};
		used[1] = 1;
		while(1){
			double MN = infty;
			int arg = -1;
			for(int i = 2; i <= N; i++){
				if(used[i]) continue;
				if(estm[i] < MN){
					MN = estm[i];
					arg = i;
				}
			}
			used[arg] = 1;
			if(arg == N) break;
			for(int i = 2; i <= N; i++){
				if(used[i]) continue;
				double newEstm = mx(dist[arg][i], estm[arg]);
				if(newEstm < estm[i]) estm[i] = newEstm;
			}
		}
		printf("%.2lf\n", estm[N]);
	}
	return 0;
}