Problem: In a far away galaxy there are n inhabited planets, numbered with numbers from 1 to n. They are located at large distances from each other, that's why the communication between them was very difficult until on the planet number 1 a hyperdrive was invented. As soon as this significant event took place, n - 1 spaceships were built on the planet number 1, and those ships were sent to other planets to inform about the revolutionary invention. 

Paradoxical thought it may be, but the hyperspace is represented as simple three-dimensional Euclidean space. The inhabited planets may be considered fixed points in it, and no two points coincide and no three points lie on the same straight line. The movement of a ship with a hyperdrive between two planets is performed along a straight line at the constant speed, the same for all the ships. That's why the distance in the hyperspace are measured in hyperyears (a ship with a hyperdrive covers a distance of s hyperyears in s years).

When the ship reaches an inhabited planet, the inhabitants of the planet dissemble it, make n - 2 identical to it ships with a hyperdrive and send them to other n - 2 planets (except for the one from which the ship arrived). The time to make a new ship compared to the time in which they move from one planet to another is so small that it can be disregarded. New ships are absolutely identical to the ones sent initially: they move at the same constant speed along a straight line trajectory and, having reached a planet, perform the very same mission, i.e. are dissembled to build new n - 2 ships and send them to all the planets except for the one from which the ship arrived. Thus, the process of spreading the important news around the galaxy continues.

However the hyperdrive creators hurried to spread the news about their invention so much that they didn't study completely what goes on when two ships collide in the hyperspace. If two moving ships find themselves at one point, they provoke an explosion of colossal power, leading to the destruction of the galaxy!

Your task is to find the time the galaxy will continue to exist from the moment of the ships' launch from the first planet.

Input

The first line contains a number n (3 ≤ n ≤ 5000) — the number of inhabited planets in the galaxy. The next n lines contain integer coordinates of the planets in format "xi yi zi" ( - 104 ≤ xi, yi, zi ≤ 104). 

Output

Print the single number — the solution to the task with an absolute or relative error not exceeding 10 - 6.

Examples

Input

4
0 0 0
0 0 1
0 1 0
1 0 0


Output

1.7071067812

Solution (in JAVA):

Solution:
import java.io.*;

//School Team Contest #2 (Winter Computer School 2010/11), D
public class Hyperdrive {

	private static final int DIMENSIONALITY = 3;
	private static final double E = 1e-8;
    public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("/home/kite/input.txt"));
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(r.readLine());
		int a[][] = new int[n][DIMENSIONALITY];
		for(int i = 0; i < n; i++) {
			String ss[] = r.readLine().split("\\s+");
			assert ss.length == DIMENSIONALITY;
			for(int x = 0; x < DIMENSIONALITY; x++)
				a[i][x] = Integer.parseInt(ss[x]);
		}

		/*
		double d[][] = new double[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++)
				d[i][j] = d[j][i] = distance(a[i], a[j]);
		}
		*/
		double d[][] = new double[1][n];
		for(int i = 0; i < n; i++)
			d[0][i] = distance(a[0], a[i]);

		double min = Double.MAX_VALUE;
		for(int i = 1; i < n - 1; i++) {
			for(int j = i + 1; j < n; j++) {
				//double time = Math.max(d[0][i], d[0][j]) + (d[i][j] - Math.abs(d[0][i] - d[0][j])) / 2;
				double time = Math.max(d[0][i], d[0][j]) + (distance(a[i], a[j]) - Math.abs(d[0][i] - d[0][j])) / 2;
				if(time < min)
					min = time;
			}
		}

		/*
		for(int i1 = 0; i1 < n - 1; i1++) {
			for(int j1 = i1 + 1; j1 < n; j1++) {
				for(int i2 = i1 + 1; i2 < n - 1; i2++) {
					if(i2 == j1)
						continue;
					for(int j2 = i2 + 1; j2 < n; j2++) {
						if(j2 == j1)
							continue;
						double p[] = intersect(a[i1], a[j1], a[i2], a[j2]);
						if(p != null) {
							double time1 = Math.min(d[0][i1] + distance(a[i1], p), d[0][j1] + distance(a[j1], p));
							double time2 = Math.min(d[0][i2] + distance(a[i2], p), d[0][j2] + distance(a[j2], p));
							if(Math.abs(time1 - time2) < E) {
								double time = time1 + time2 / 2;
								if(time < min)
									min = time;
							}
						}
					}
				}

			}
		}
		*/
		System.out.println(min);
    }

	private static double distance(int[] point1, int[] point2) {
		if(point1.length != DIMENSIONALITY || point2.length != DIMENSIONALITY)
			throw new IllegalArgumentException();
		int sum = 0;
		for(int x = 0; x < DIMENSIONALITY; x++) {
			int temp = point1[x] - point2[x];
			sum += temp * temp;
		}
		return Math.sqrt(sum);
	}

	private static double distance(int[] point1, double[] point2) {
		if(point1.length != DIMENSIONALITY || point2.length != DIMENSIONALITY)
			throw new IllegalArgumentException();
		double sum = 0;
		for(int x = 0; x < DIMENSIONALITY; x++) {
			double temp = point1[x] - point2[x];
			sum += temp * temp;
		}
		return Math.sqrt(sum);
	}

	private static double[] intersect(int[] point1, int[] point2, int[] point3, int[] point4) {
		if(point1.length != point2.length || point2.length != point3.length || point3.length != point4.length)
			throw new IllegalArgumentException();
		if(point1.length != 3)
			throw new UnsupportedOperationException();
		double a[][] = new double[][] {
			{1, 0, 0, point1[0] - point2[0], 0, point1[0]},
			{0, 1, 0, point1[1] - point2[1], 0, point1[1]},
			{0, 0, 1, point1[2] - point2[2], 0, point1[2]},
			{1, 0, 0, 0, point3[0] - point4[0], point3[0]},
			{0, 1, 0, 0, point3[1] - point4[1], point3[1]},
			{0, 0, 1, 0, point3[2] - point4[2], point3[2]},
		};
		return jordanGauss(a) ? new double[] {a[0][a[0].length - 1], a[1][a[1].length - 1], a[2][a[2].length - 1]} : null;
	}

	private static boolean jordanGauss(double[][] a) {
		final int n = a.length;
		final int m = a[0].length;
		for(int i = 1; i < n; i++) {
			if(a[i].length != m)
				throw new IllegalArgumentException();
		}
		if(n < m - 1)
			throw new IllegalArgumentException();
		for(int i, j, k = 0, l; k < n; k++) {
			if(k >= m - 1) {
				if(a[k][m - 1] != 0)
					return false;
				continue;
			}
			for(l = k, i = k + 1; i < n; i++) {
				if(Math.abs(a[i][k]) > Math.abs(a[l][k]))
					l = i;
			}
			if(a[l][k] == 0)
				return false;
			if(l != k) {
				double[] t = a[k];
				a[k] = a[l];
				a[l] = t;
			}
			for(j = k + 1; j < m; j++)
				a[k][j] /= a[k][k];
			a[k][k] = 1;
			for(i = 0; i < n; i++) {
				if(i != k) {
					for(j = k + 1; j < m; j++)
						a[i][j] -= a[k][j] * a[i][k];
					a[i][k] = 0;
				}
			}
		}
		return true;
	}

}