The time for an interstellar trade route has come! The plaque sent out on the Pioneer probes was decoded by an alien civilization, and they have imparted to us the secrets of interstellar  travel. Your job is to find the two stars nearest to each other in our galaxy, and begin your trade route between these two star systems. Well assume that you can pick any two stars to begin your trade route; you don't have to start at Earth. Being as our galaxy has a lot of stars (up to 400 billion), your algorithm will need to be efficient. 

The galaxy is 3-dimensional, so you’ll need to handle star locations in 3D space. The coordinates will range from -50,000 to +50,000 (the Milky Way is 100,000 light-years in diameter) . Your trading ships cannot travel more than 10,000 light-years, and any input case that has no stars closer than this will need to indicate such.

Input

The input will consist of a number of test cases (more than one per  file!) .  The first line of each test  case  will contain n, the number of stars for that case: 2 < n < 100, 000. The following n lines will contain the (x,y,z) coordinates of successive stars. Each x, y, and z coordinate will be a real number with a minimum value of -50,000 and a mazimum value of 50,000. The coordinates will be given to two decimal places of accuracy. The input will terminate when n=0

Output

For each test case, your output should contain a single line that is the minimum distance  between  two  points, to four digits of accuracy after the decimal point. You should not print  the stars that  are closest; only the distance. If there are no points closer than a distance of 10,000, you should print out infinity.

This assignment has been answered 4 times in private sessions.

Or buy a ready solution below.