ISLHOP  Island Hopping
The company Pacific Island Net (PIN) has identified several small island groups in the Pacific that do not have a fast internet connection. PIN plans to tap this potential market by offering internet service to the island inhabitants. Each groups of islands already has a deepsea cable that connects the main island to the closest internet hub on the mainland (be it America, Australia or Asia). All that remains to be done is to connect the islands in a group to each other. You must write a program to help them determine a connection procedure.
For each island, you are given the position of its router and the number of island inhabitants. In the figure, the dark dots are the routers and the numbers are the numbers of inhabitants. PIN will build connections between pairs of routers such that every router has a path to the main island. PIN has decided to build the network such that the total amount of cable used is minimal. Under this restriction, there may be several optimal networks. However, it does not matter to PIN which of the optimal networks is built.
PIN is interested in the average time required for new customers to access the internet, based on the assumption that construction on all cable links in the network begins at the same time. Cable links can be constructed at a rate of one kilometer of cable per day. As a result, shorter cable links are completed before the longer links. An island will have internet access as soon as there is a path from the island to the main island along completed cable links. If m_{i} is the number of inhabitants of the ith island and t_{i} is the time when the island is connected to the internet, then the average connection time is:
Input
The input consists of several descriptions of groups of islands. The first line of each description contains a single positive integer n, the number of islands in the group (n <= 50). Each of the next n lines has three integers x_{i}, y_{i}, m_{i}, giving the position of the router (x_{i}, y_{i}) and number of inhabitants m_{i}(m_{i} > 0) of the islands. Coordinates are measured in kilometers. The first island in this sequence is the main island.
The input is terminated by the number zero on a line by itself.
Output
For each group of islands in the input, output the sequence number of the group and the average number of days until the inhabitants are connected to the internet. The number of days should have two digits to the right of the decimal point. Use the output format in the sample given below.
Place a blank line after the output of each test case.
Example
Input: 7 11 12 2500 14 17 1500 9 9 750 7 15 600 19 16 500 8 18 400 15 21 250 0 Output: Island Group: 1 Average 3.20
hide comments
qhnxhimfqy:
20190301 19:50:19
Are the inhabitants of the mainland counted in the total population for calculating the average? My answer sometimes is off by 0.1  0.2. 

Arya08:
20151026 14:38:59
what is the range of xi , yi and mi(upper limit) 

Ashutosh Singla:
20131021 21:39:45
There can be more than one, island at one position. 

:D:
20110407 06:18:48
It can be proven than for every optimal network average connection time is the same. If you really want you can count the average average connection time over all optimal networks and it will also work :) 

Peter:
20090816 21:57:59
What is the goal of this problem? To find the minimum average connection time provided an optimal network is built? 

Mostafa Saad:
20090628 06:18:32
Output section is titled wrongly.

Added by:  Fudan University Problem Setters 
Date:  20080103 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM/ICPC World Final 2002 (unofficial testdata) 