Problem: Anchored Balloon

A balloon placed on the ground is connected to one or more anchors on the ground with ropes. Each rope is long enough to connect the balloon and the anchor. No two ropes cross each other. Figure E-1 shows such a situation.

<image>
Figure E-1: A balloon and ropes on the ground

Now the balloon takes off, and your task is to find how high the balloon can go up with keeping the rope connections. The positions of the anchors are fixed. The lengths of the ropes and the positions of the anchors are given. You may assume that these ropes have no weight and thus can be straightened up when pulled to whichever directions. Figure E-2 shows the highest position of the balloon for the situation shown in Figure E-1.

<image>
Figure E-2: The highest position of the balloon

Input

The input consists of multiple datasets, each in the following format.

> n
>  x1 y1 l1
>  ...
>  xn yn ln
>

The first line of a dataset contains an integer n (1 ≤ n ≤ 10) representing the number of the ropes. Each of the following n lines contains three integers, xi, yi, and li, separated by a single space. Pi = (xi, yi) represents the position of the anchor connecting the i-th rope, and li represents the length of the rope. You can assume that −100 ≤ xi ≤ 100, −100 ≤ yi ≤ 100, and 1 ≤ li ≤ 300. The balloon is initially placed at (0, 0) on the ground. You can ignore the size of the balloon and the anchors.

You can assume that Pi and Pj represent different positions if i ≠ j. You can also assume that the distance between Pi and (0, 0) is less than or equal to li−1. This means that the balloon can go up at least 1 unit high.

Figures E-1 and E-2 correspond to the first dataset of Sample Input below.

The end of the input is indicated by a line containing a zero.

Output

For each dataset, output a single line containing the maximum height that the balloon can go up. The error of the value should be no greater than 0.00001. No extra characters should appear in the output.

Sample Input


3
10 10 20
10 -10 20
-10 10 120
1
10 10 16
2
10 10 20
10 -10 20
2
100 0 101
-90 0 91
2
0 0 53
30 40 102
3
10 10 20
10 -10 20
-10 -10 20
3
1 5 13
5 -3 13
-3 -3 13
3
98 97 168
-82 -80 193
-99 -96 211
4
90 -100 160
-80 -80 150
90 80 150
80 80 245
4
85 -90 290
-80 -80 220
-85 90 145
85 90 170
5
0 0 4
3 0 5
-3 0 5
0 3 5
0 -3 5
10
95 -93 260
-86 96 211
91 90 177
-81 -80 124
-91 91 144
97 94 165
-90 -86 194
89 85 167
-93 -80 222
92 -84 218
0


Output for the Sample Input


17.3205081
16.0000000
17.3205081
13.8011200
53.0000000
14.1421356
12.0000000
128.3928757
94.1879092
131.1240816
4.0000000
72.2251798






Example

Input

3
10 10 20
10 -10 20
-10 10 120
1
10 10 16
2
10 10 20
10 -10 20
2
100 0 101
-90 0 91
2
0 0 53
30 40 102
3
10 10 20
10 -10 20
-10 -10 20
3
1 5 13
5 -3 13
-3 -3 13
3
98 97 168
-82 -80 193
-99 -96 211
4
90 -100 160
-80 -80 150
90 80 150
80 80 245
4
85 -90 290
-80 -80 220
-85 90 145
85 90 170
5
0 0 4
3 0 5
-3 0 5
0 3 5
0 -3 5
10
95 -93 260
-86 96 211
91 90 177
-81 -80 124
-91 91 144
97 94 165
-90 -86 194
89 85 167
-93 -80 222
92 -84 218
0


Output

17.3205081
16.0000000
17.3205081
13.8011200
53.0000000
14.1421356
12.0000000
128.3928757
94.1879092
131.1240816
4.0000000
72.2251798

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<bits/stdc++.h>
#include<iomanip>
#include<queue>
#include<string>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<algorithm>
#include<functional>	//for "greater<type>"
#include<cmath>
using namespace std;
#define pb push_back
#define fi first
#define sc second
#define mp make_pair
#define is insert	//?????????

#define DEBUG 1

#define INF (1.0/0.0)
#define EPS 1e-8
#define PI 3.1415926535
#define EQ(x, y) (abs((x)-(y))<EPS)
#define GE(x, y) ((x)>(y)||EQ(x, y))
#define LE(x, y) ((x)<(y)||EQ(x, y))
#define X real()
#define Y imag()

typedef complex<double> point;
typedef point vec;
typedef array<point, 2> line;
typedef vector<point> poly;

struct circle {
	point c;
	double r;
};

enum geometry {ABC=-2, CW, ON_LINE, CCW, CAB, OUTSIDE, INSIDE, ERROR}; 

namespace std {
	bool operator<(point a, point b) {
		if (!EQ(a.X, b.X)) return a.X < b.X;
		if (!EQ(a.Y, b.Y)) return a.Y < b.Y;
		return false;
	}

	bool operator>(point a, point b) {
		return b<a;
	}

	bool operator<=(point a, point b) {
		return !(a>b);
	}
}

double dot(point a, point b) {
	return (conj(a)*b).X;
}

double cross(point a, point b) {
	return (conj(a)*b).Y;
}

geometry ccw(point a, point b, point c) {
	b -= a;
	c -= a;
	if (cross(b, c) > EPS) return CCW; // ccw
	if (cross(b, c) < -EPS) return CW; // cw
	if (dot(b, c) < 0) return CAB; // c - a - b
	if (norm(b) < norm(c)) return ABC; // a - b - c
	return ERROR;
}

point proj(line l, point p) {
	point v = l[1]-l[0];
	double ratio = dot(v, p-l[0]) / norm(v);
	return l[0] + ratio*v;
}

point refl(line l, point p) {
	return p + (proj(l, p) - p) * 2.0;
}

vec rotate(vec v, double r) {
	return v*vec(cos(r), sin(r));
}

vec Normalvec(line l){
	vec v=(vec)l[1]-l[0];
	return vec (v.Y,-v.X);
}

bool IsOrthogonal(line l, line m) {
	vec v1 = l[1]-l[0];
	vec v2 = m[1]-m[0];
	return EQ(dot(v1, v2), 0.0);
}

bool IsParallel(line l, line m) {
	vec v1 = l[1]-l[0];
	vec v2 = m[1]-m[0];
	return EQ(cross(v1, v2), 0.0);
}

bool IntersectLL(line l, line m) {
	if (!EQ(cross(l[1]-l[0], m[1]-m[0]), 0.0)) return true;
	if (EQ(cross(l[1]-l[0], m[0]-l[0]), 0.0)) return true;
	return false;
}

bool IntersectLS(line l, line s) {
	point b = l[0];
	vec v = l[1]-l[0];
	return cross(v, s[0]-b)*cross(v, s[1]-b) < EPS;
}

bool IntersectSS(line s, line t) {
	if (ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) > 0) return false;
	if (ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) > 0) return false;
	return true;
}

bool IntersectLP(line l, point p) {
	return EQ(cross(l[1]-p, l[0]-p), 0.0);
}

bool IntersectSP(line s, point p) {
	return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS;
}

double DistL(line l) {
	return abs(l[0]-l[1]);
}

double DistLP(line l, point p) {
	return abs(p - proj(l, p));
}

double DistLL(line l, line m) {
	if (!IntersectLL(l, m)) return 0;
	return DistLP(l, m[0]);
}

double DistLS(line l, line s) {
	if (IntersectLS(l, s)) return 0;
	return min(DistLP(l, s[0]), DistLP(l, s[1]));
}

double DistSP(line s, point p) {
	point r = proj(s, p);
	if (IntersectSP(s, r)) return abs(r - p);
	return min(abs(s[0]-p), abs(s[1]-p));
}

double DistSS(line s, line t) {
	if (IntersectSS(s, t)) return 0;

	double a = min(DistSP(s, t[0]), DistSP(s, t[1]));
	double b = min(DistSP(t, s[0]), DistSP(t, s[1]));
	return min(a, b);
}

line PerpendBisect(line seg) {
	point mid = (seg[0]+seg[1])/2.0;
	return line{mid, mid+(seg[1]-seg[0])*vec(0, 1)};
}

point CrosspointLL(line l, line m) {
	double A = cross(l[1]-l[0], m[1]-m[0]);
	double B = cross(l[1]-l[0], l[1]-m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0];
	if (abs(A) < EPS) assert(0);
	return m[0] + B / A * (m[1]-m[0]);
}

vector<point> CrosspointCL(circle c, line l) {
	vector<point> ret;
	double d = DistLP(l, c.c);
	if (EQ(d, c.r)) {
		ret.emplace_back(proj(l, c.c));
	} else if (d < c.r) {
		double ratio = sqrt(c.r*c.r - d*d);
		vec sgn = (l[0]-l[1]) / abs(l[0]-l[1]);
		ret.emplace_back(proj(l, c.c) + ratio*sgn);
		ret.emplace_back(proj(l, c.c) - ratio*sgn);
	}

	return ret;
}

vector<point> CrosspointCS(circle c, line s) {
	vector<point> ret;
	vector<point> res = CrosspointCL(c, s);
	if (s[0] > s[1]) swap(s[0], s[1]);
	for (point p : res) {
		if (s[0] <= p && p <= s[1]) ret.emplace_back(p);
	}
	return ret;
}

vector<point> CrosspointCC(circle c1, circle c2) {
	vector<point> ret;
	double d = abs(c1.c - c2.c);
	double rc = (d*d + c1.r*c1.r - c2.r*c2.r) / (2*d);
	double dfr = c1.r*c1.r - rc*rc;

	if (EQ(dfr, 0.0)) dfr = 0.0;
	else if(dfr < 0.0) return ret;

	double rs = sqrt(dfr);
	vec sgn = (c2.c - c1.c) / d;
	ret.emplace_back(c1.c + sgn*point(rc, rs));
	if (dfr > 0.0) ret.emplace_back(c1.c + sgn*point(rc, -rs));
	return ret;
}

// Get the intersection of a circle and a segment, which is obviously a segment
line CapCS(circle c, line s) {
	point inf(INF, INF);
	vector<point> cros = CrosspointCS(c, s);
	if (cros.empty()) return line{inf, inf};

	if (cros.size() == 1) {
		double ad = abs(s[0]-c.c);
		double bd = abs(s[1]-c.c);
		if (ad < min(bd, c.r)) cros.emplace_back(s[0]);
		else if (bd < min(ad, c.r)) cros.emplace_back(s[1]);
		else {
			point p = cros[0];
			cros.emplace_back(p); // avoid an undefined behavior
		}
	}

	if (cros[1] < cros[0]) {
		swap(cros[0], cros[1]);
	}

	return line{cros[0], cros[1]};
}

geometry Positioningpoint(poly poly, point p) {
	bool in = false;
	int n = poly.size();
	for (int i=0; i<n; i++) {
		point a = poly[i];
		point b = poly[(i+1)%n];
		vec u = a - p;
		vec v = b - p;

		if (u.Y > v.Y) swap(u, v);

		double cr = cross(u, v);
		if (u.Y <= 0 && 0 < v.Y && cr > EPS) in ^= 1;
		if (IntersectSP({a, b}, p)) return ON_LINE;
	}

	if (in) return INSIDE;
	return OUTSIDE;
}

// Note that ccw(a, b, c) != CCW when a, b, c are colinear
poly GrahamScan(vector<point> ps) {//Get convex hull.
	if (ps.size() <= 2) return ps;

	int k = 0;
	int n = ps.size();
	poly ret(n*2);

	sort(ps.begin(), ps.end());
	for (int i=0; i<n; i++) {
		while (k > 1 && ccw(ret[k-2], ret[k-1], ps[i]) != CCW) k--;
		ret[k++] = ps[i];
	}

	int k_ = k;
	for (int i=n-1; i>=0; i--) {
		while (k > k_ && ccw(ret[k-2], ret[k-1], ps[i]) != CCW) k--;
		ret[k++] = ps[i];
	}

	ret.resize(k-1);
	return ret;
}

bool IsConvex(poly ps) {
	return GrahamScan(ps).size() == ps.size();
}

poly CapConvexes(poly pp, poly qq) {
#if DEBUG
	assert (IsConvex(pp));
	assert (IsConvex(qq));
#endif

	poly ret;
	int a = 0;
	int b = 0;
	int aa = 0;
	int bb = 0;
	int n = pp.size();
	int m = qq.size();
	enum {PIN, QIN, UNKNOWN} in = UNKNOWN;

	auto forward_a = [&](bool put) {
		if (put && in == PIN) ret.emplace_back(pp[a]);
		a = (a+1)%n;
		aa++;
	};

	auto forward_b = [&](bool put) {
		if (put && in == QIN) ret.emplace_back(qq[b]);
		b = (b+1)%m;
		bb++;
	};

	auto intersect_1pt = [](point &a, point &b, point &c, point &d, point &r) {
		double D =	cross(b - a, d - c);
		if (EQ(D, 0)) return false;
		double t =	cross(c - a, d - c) / D;
		double s = -cross(a - c, b - a) / D;
		r = a + t * (b - a);
		return GE(t, 0) && LE(t, 1) && GE(s, 0) && LE(s, 1);
	};

	do {
		int apre = (a+n-1)%n;
		int bpre = (b+m-1)%m;
		double C = cross(pp[a]-pp[apre], qq[b]-qq[bpre]);
		double A = cross(pp[apre]-qq[b], pp[a]-qq[b]);
		double B = cross(qq[bpre]-pp[a], qq[b]-pp[a]);
		point r;
		if (intersect_1pt(pp[apre], pp[a], qq[bpre], qq[b], r)) {
			if (in == UNKNOWN) aa = bb = 0;
			ret.emplace_back(r);
			if (B > 0) in = PIN;
			else if (A > 0) in = QIN;
		}

		if (EQ(A, 0) && EQ(B, 0) && EQ(C, 0)) {
			if (in == PIN) forward_b(false);
			else forward_a(false);
		} else if (C >= 0) {
			if (A > 0) forward_a(true);
			else forward_b(true);
		} else {
			if (B > 0) forward_b(true);
			else forward_a(true);
		}
	} while ((aa < n || bb < m) && aa < 2*n && bb < 2*m);

	if (in == UNKNOWN) {
		if (Positioningpoint(qq, pp[0]) != OUTSIDE) return pp;
		if (Positioningpoint(pp, qq[0]) != OUTSIDE) return qq;
	}
	return ret;
}

double CalcArea(poly ps) {
	double ret = 0.0;
	for (int i=0; i<ps.size(); i++) {
		ret += cross(ps[i], ps[(i+1)%ps.size()]);
	}
	return ret/2.0;
}

// Convex* requires the elements of ps to be arranged counter clockwise.
pair<int, int> ConvexDiameterApexes(poly ps) {
#if DEBUG
	assert (IsConvex(ps));
#endif

	int n = ps.size();
	int is = 0;
	int js = 0;
	for (int i=1; i<n; i++) {
		if (ps[i].Y > ps[is].Y) is = i;
		if (ps[i].Y < ps[js].Y) js = i;
	}

	int maxi, maxj;
	double maxd = norm(ps[is]-ps[js]);
	int i = is;
	int j = js;
	do {
		vec a = ps[i+1] - ps[i];
		vec b = ps[j+1] - ps[j];
		if (cross(a, b) > -EPS) j = (j+1)%n;
		else i = (i+1)%n;

		double d = norm(ps[i]-ps[j]);
		if (d > maxd) {
			maxd = d;
			maxi = i;
			maxj = j;
		}
	} while (i != is || j != js);

	return make_pair(maxi, maxj);
}

line ClosestPair(vector<point> ps) {
	auto CompareY = [](const point &a, const point &b) {
		if (a.Y != b.Y) return a.Y < b.Y;
		return a.X < b.X;
	};

	function<line(point*,int)> Rec = [&Rec, &CompareY](point *ps, int n) {
		if (n <= 1) return line{point(0, 0), point(INF, INF)};
		
		int m = n/2;
		double x = ps[m].X;
		line a = Rec(ps, m);
		line b = Rec(ps+m, n-m);
		double mind = DistL(a);
		line ret = a;
		if (DistL(b) < mind) {
			mind = DistL(b);
			ret = b;
		}

		sort(ps, ps+n, CompareY);
		vector<point> qs;
		qs.reserve(n);
		for (int i=0; i<n; i++) {
			if (abs(ps[i].X - x) >= mind) continue;

			for (int j=0; j<qs.size(); j++) {
				point p1 = ps[i];
				point p2 = qs[qs.size()-1-j];
				if (p1.Y - p2.Y >= mind) break;

				double d = abs(p1-p2);
				if (mind > d) {
					mind = d;
					ret = line{p1, p2};
				}
			}

			qs.emplace_back(ps[i]);
		}

		return ret;
	};

	int n = ps.size();
	assert (n >= 2);
	sort(ps.begin(), ps.end());
	return Rec(&ps[0], n);
}

// Convex* requires the elements of ps to be arranged counter clockwise.
// <left, right> or <upper, lower>
pair<poly, poly> CutConvex(poly ps, line l) {
#if DEBUG
	assert (IsConvex(ps));
#endif

	//if (l[0].Y > l[1].Y) swap(l[0], l[1]);
	//else if (EQ(l[0].Y, l[1].Y) && l[0].X > l[1].X) swap(l[0], l[1]);

	poly left;
	poly right;
	for (int i=0; i<ps.size(); i++) {
		point a = ps[i];
		point b = ps[(i+1)%ps.size()];

		if (ccw(l[0], l[1], a) != CW) left.emplace_back(a);
		else right.emplace_back(a);

		line m{a, b};
		if (IntersectLS(l, m)) {
			point p = CrosspointLL(l, m);
			left.emplace_back(p);
			right.emplace_back(p);
		}
	}

	return make_pair(left, right);
}

circle Circum(point a, point b, point c) {
	circle ret{{INF, INF}, 0.0};
	line l{a, b};
	line m{b, c};
	line lp = PerpendBisect(l);
	line mp = PerpendBisect(m);
	if (IsParallel(lp, mp)) return ret;

	ret.c = CrosspointLL(lp, mp);
	ret.r = abs(a-ret.c);
	return ret;
}

vector<point> Tangentpoints(circle c, point p) {
	vector<point> ret;
	double d = abs(c.c-p);
	if (EQ(d, c.r)) {
		ret.emplace_back(p);
		return ret;
	}

	if (d < c.r) return ret;

	vec v = (p-c.c)/d*c.r;
	double t = acos(c.r/d);
	ret.emplace_back(c.c + rotate(v, t));
	ret.emplace_back(c.c + rotate(v, -t));
	return ret;
}

vector<line> CommonTangents(circle p, circle q) {
#if DEBUG
	assert(!EQ(p.c, q.c) || !EQ(p.r, q.r));
#endif

	double pr = p.r;
	double qr = q.r;
	point pc = p.c;
	point qc = q.c;
	double d = abs(pc - qc);
	double dr = abs(pr - qr);
	double sr = abs(pr + qr);

	vector<line> ret;
	if (EQ(d, sr)) {//If the 2 circles tangent exclusively,
		point cp = (pc * qr + qc * pr) / sr;
		vec v = cp - pc;
		ret.emplace_back(line{cp, cp + v*vec(0, 1)});
	} else if (d > sr) {//If the 2 have no intersection,
		point cp = (pc * qr + qc * pr) / sr;
		vector<point> pts = Tangentpoints(p, cp);
		vector<point> qts = Tangentpoints(q, cp);
		for (int i=0; i<2; i++) {
			line l{pts[0], qts[i]};
			if(IntersectLP(l, cp)) {
				ret.emplace_back(l);
				ret.emplace_back(line{pts[1], qts[i^1]});
			}
		}
	} 

	if (EQ(d, dr)) {//If the 2 tangent inclusively,
		point cp = pc + (pc-qc) / (qr-pr) * pr;
		vec v = cp - pc;
		ret.emplace_back(line{cp, cp + v*vec(0, 1)});
	} else if (d > dr) {//If the 2 intersect,
		if (EQ(pr, qr)) {
			point v = (qc - pc) / d * pr;
			v *= point(0, 1);
			ret.emplace_back(line{pc+v, qc+v});
			ret.emplace_back(line{pc-v, qc-v});
		} else {
			point cp = pc + (qc-pc) * pr / (pr-qr);
			vector<point> pts = Tangentpoints(p, cp);
			vector<point> qts = Tangentpoints(q, cp);
			for (int i=0; i<2; i++) {
				line l{pts[0], qts[i]};
				if(IntersectLP(l, cp)) {
					ret.emplace_back(l);
					ret.emplace_back(line{pts[1], qts[i^1]});
					break;
				}
			}
		}
	} 

	return ret;
}

typedef pair<point,double> ppd;

point p[10];
double l[10];
ppd h[10][10];

ppd ans2(int i,int j){
	if(h[i][j].sc!=0){
		return h[i][j];
	}
	double r=abs(p[i]-p[j]);
	ppd ret;
	if(abs(l[i]*l[i]-l[j]*l[j])>=r*r){
		if(l[i]>l[j]){
			ret.fi=p[j];
			ret.sc=l[j];
		}else{
			ret.fi=p[i];
			ret.sc=l[i];
		}
	}else{
		circle c,d;
		c.c=p[i];
		c.r=l[i];
		d.c=p[j];
		d.r=l[j];
		vector<point> v=CrosspointCC(c,d);
		ret.fi=(v[0]+v[1])/2.0;
		ret.sc=abs(v[0]-v[1])/2.0;
	}
	h[i][j]=ret;
	h[j][i]=ret;
	return ret;
}

void solve(int n){
	double ans=301;
	int i[5];
	for(int j=0;j<n;++j){
		int x,y;
		cin>>x>>y>>l[j];
		p[j]=point (x,y);
		fill(h[j],h[j]+n,mp(0,0));
	}
	if(n==1){//for the sake of avoiding bugs
		cout<<fixed<<setprecision(5)<<l[0]<<endl;
		return;
	}else if(n==2){//for the same purpose
		cout<<fixed<<setprecision(5)<<ans2(0,1).sc<<endl;
		return;
	}
	for(i[0]=0;i[0]<n-2;++i[0]){
		i[3]=i[0];
		for(i[1]=i[0]+1;i[1]<n-1;++i[1]){
			i[4]=i[1];
			for(i[2]=i[1]+1;i[2]<n;++i[2]){
				bool f=false;
				ppd pa[4];
				vector<line> m;
				pa[0]=ans2(i[0],i[1]),pa[1]=ans2(i[1],i[2]),pa[2]=ans2(i[2],i[0]),pa[3]=pa[0];
				for(int j=0;j<3;++j){//??????
					if(pa[j].fi==pa[j+1].fi){
						ans=min(ans,pa[j].sc);
						f=true;
						break;
					}
				}
				if(f){
					continue;
				}
				for(int j=0;j<3;++j){
					if(pa[j].fi!=p[i[j]]&&pa[j].fi!=p[i[j+1]]){
						double r=abs(pa[j].fi-p[i[j+2]]);
						if(r*r+pa[j].sc*pa[j].sc<=l[i[j+2]]*l[i[j+2]]){
							ans=min(ans,pa[j].sc);
							f=true;
							break;
						}else{
							m.pb({pa[j].fi,pa[j].fi+Normalvec({p[i[j]],p[i[j+1]]})});
						}
					}
				}
				if(f){
					continue;
				}
				point z=CrosspointLL(m[0],m[1]);
				double r=abs(z-p[i[0]]);
				ans=min(ans,sqrt(l[i[0]]*l[i[0]]-r*r));
			}
		}
	}
	cout<<fixed<<setprecision(5)<<ans<<endl;
}

int main(){
	while(true){
		int n;
		cin>>n;
		if(n==0){
			break;
		}
		solve(n);
	}
}