UVA1013 Island Hopping

#### 题目背景 PIN 已经找到了几个群岛的商机——为他们提供网络  给定每个岛屿的坐标和岛居民数。图中黑点表示他的位置，数字表示岛居民数。PIN 将会在岛间两两修建电缆，直到所有岛屿都可以到达主岛。PIN 决定要用最少的电缆连接网络。这可能存在多个最优解，但 PIN 感兴趣的是客户连接到网络的平均时间。假设所有电缆都同时开始建设，每天每条电缆可以建造一公里。$m_i$ 代表岛上居民数，$t_i$ 是岛屿连接到互联网的时间。那么平均时间可以表示为：$\frac{\sum t_i\times m_i}{\sum m_i}$。

输入包括多组数据，读到 $0$ 为止。 每组数据的第一行是一个正整数 $n$ ，表示孤岛数，接下来 $n$ 行，每行包括三个正整数 $x_i$，$y_i$，$m_i$，代表第 $i$ 座岛屿的坐标和总居民数，坐标的单位是千米，每组数据输入的第一个岛屿是主岛。

对于每组数据，输出居民连接上网络的平均天数，保留两位小数。具体参考样例。 每组数据输出完请空一行 #### 样例 输入 ``` 7 11 12 2500 14 17 1500 9 9 750 7 15 600 19 16 500 8 18 400 15 21 250 0 ``` 输出（亲测，与PDF描述不符） ``` Island Group: 1 Average 3.20 ```

对于任意的 $n$, $n\leq 50$, $m_i>0$