All the cells must be connected, since crew members should be able to walk from any cell to any other cell. They can walk from a cell A to another cell B, if, (1) A and B are touching each other or overlapping, (2) A and B are connected by a `corridor', or (3) there is a cell C such that walking from A to C, and also from B to C are both possible. Note that the condition (3) should be interpreted transitively.

You are expected to design a configuration, namely, which pairs of cells are to be connected with corridors. There is some freedom in the corridor configuration. For example, if there are three cells A, B and C, not touching nor overlapping each other, at least three plans are possible in order to connect all three cells. The first is to build corridors A-B and A-C, the second B-C and B-A, the third C-A and C-B. The cost of building a corridor is proportional to its length. Therefore, you should choose a plan with the shortest total length of the corridors.

You can ignore the width of a corridor. A corridor is built between points on two cells' surfaces. It can be made arbitrarily long, but of course the shortest one is chosen. Even if two corridors A-B and C-D intersect in space, they are not considered to form a connection path between (for example) A and C. In other words, you may consider that two corridors never intersect.

n 
x1 y1 z1 r1 
x2 y2 z2 r2 
... 
xn yn zn rn

The first line of a data set contains an integer n, which is the number of cells. n is positive, and does not exceed 100.

The following n lines are descriptions of cells. Four values in a line are x-, y- and z-coordinates of the center, and radius (called r in the rest of the problem) of the sphere, in this order. Each value is given by a decimal fraction, with 3 digits after the decimal point. Values are separated by a space character.

Each of x, y, z and r is positive and is less than 100.0.

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

Note that if no corridors are necessary, that is, if all the cells are connected without corridors, the shortest total length of the corridors is 0.000.

题目意思：给出一些球体的球心坐标和半径，需要用最短的路径连通这些球体，（这里忽略路径的宽度），先让你求出连通这些球体的最短路径。 

注意：连通时不是连通球心，而是 球面。

#include<stdio.h>

#include<string.h>

#include<math.h>

#define INF 0x3ffffff

int n;

double x[110],y[110],z[110],r[110];

double map[110][110];

double low[110];

int vis[110];

double fun(double x1,double y1,double z1,double r1,double x2,double y2,double z2,double r2)

{

	if(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))-r1-r2<=0)

	    return 0;

	else

	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))-r1-r2;

}

void init()

{

	int i,j;

	for(i=1;i<=n;i++)

	{

		for(j=1;j<=n;j++)

		{

			if(i==j)

			map[i][j]=0;

			else

			map[i][j]=INF;

		}

	}

}

void getmap()

{

	int i,j;

	for(i=1;i<=n;i++)

		scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);

    for(i=1;i<n;i++)

    {

    	for(j=i+1;j<=n;j++)

    	map[i][j]=map[j][i]=fun(x[i],y[i],z[i],r[i],x[j],y[j],z[j],r[j]);

	}

}

void prime()

{

	int i,j,next;

	double min,mindis=0;

	int ok=0;

	memset(vis,0,sizeof(vis));

	for(i=1;i<=n;i++)

	low[i]=map[1][i];

	vis[1]=1;

	for(i=1;i<n;i++)

	{

		min=INF;

		for(j=1;j<=n;j++)

	    {

	    	if(!vis[j]&&min>low[j])

	    	{

	    		min=low[j];

	    		next=j;

			}

		}

		mindis+=min;

		vis[next]=1;

		for(j=1;j<=n;j++)

		{

			if(!vis[j]&&low[j]>map[next][j])

			  low[j]=map[next][j];

		}

	}

	printf("%.3f\n",mindis);

}

int main()

{

	while(scanf("%d",&n),n)

	{

		init();

	    getmap();

	    prime();

	}

	return 0;

}