题目描述

你是空间站工程团队的一员，负责在空间站建造过程中完成一项编程任务。

空间站由多个单元舱（cell）组成，所有单元舱均为球形，但尺寸不一定相同。每个单元舱在空间站成功入轨后即被固定在预定位置。奇特的是，两个单元舱可能相互接触甚至部分重叠，极端情况下一个单元舱可能完全包裹另一个单元舱。

所有单元舱必须保持连通性，以确保宇航员能在任意两个单元舱之间通行。通行规则如下：

1. 直接连通：单元舱$A$与$B$接触或重叠。
2. 走廊连接：通过建造**走廊（corridor）**连接$A$和$B$。
3. 间接连通：存在单元舱$C$，使得$A$与$C$、$B$与$C$均连通（满足传递性）。

任务要求

设计走廊的连接方案，使得：

• 所有单元舱连通。
• 总走廊长度最短（走廊成本与其长度成正比）。
• 走廊可视为无宽度的直线，连接两单元舱表面，且长度取最短可能值。
• 若无需走廊即可连通（如所有单元舱已直接接触/重叠），输出$0.000$。

输入格式

• 每个测试用例格式如下：

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

  • $n$：单元舱数量（$1 \leq n \leq 100$）。
  • $x_i, y_i, z_i$：第$i$个单元舱中心的三维坐标（保留$3$位小数）。
  • $r_i$：第$i$个单元舱的半径（保留$3$位小数）。
  • 坐标和半径均为正数且小于$100.0$。
• 输入以单独一行的$0$结束。

输出格式

对每个测试用例，输出一行：最短走廊总长度（保留$3$位小数，误差不超过$0.001$）。

样例输入

3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0

样例输出

20.000
0.000
73.834