Houston, We've Got a Problem!
By IX Maratona de Programação IME-USP, 2005 
Brazil
By IX Maratona de Programação IME-USP, 2005 Brazil
On July 1st, 1947, a strange object was detected by american force radars installed on Roswell, White Sands and Alamogordo. The tremendous speed and the erratic moves of the object indicated that it wasn't an airplane or meteorite. Four days later, a shepherd and a group of archaeologists found remains of a crashed object to the north of Roswell. Thereafter, american authorities step in and transport the remains of the object to Fort Worth, Texas. They said the wreckage were simply remains of an experimental weather balloon. Many people, however, think it was the remains of an unidentified flying object (UFO). Many years have passed since then, and the case continues to attract attention and generate controversy.
A group of ufologists rooted on San Antonio, a texan city located south-southwest of Fort Worth, is convinced that extraterrestrial beings have visited the region frequently ever since. After a lot of research, the ufologists found that they could build an alternative communication network to try to contact the ETs. Such a network would use remains of the old telegraph system from the Texas desert and its alternativity comes from the attempt to avoid, according to them, the intromission of the aforementioned authorities.
After a thorough survey (that identified posts, wirings, capacitors, transformers, etc.), the ufologists realized that information transmitted through certain parts of the old telegraph structure had worse quality than others. Based on statistical samples, they obtained, for some pairs of points u and v of the old network, a probability puv of having interference on information transmitted between u and v. Knowing that you would be in the region in April next year, they asked you to build a program to identify the smaller set of paths to be used so that (i) all the desired points are interconnected (even indirectly), and (ii) the total probability of interference on the messages sent through this network is minimum. Eager to discover the truth (which "is out there..."), you promptly responded to the request.
Your program must be prepared to deal with various instances. Each instance have the following format. On the first line, are specified two integers 0 ≤ n ≤ 100 and 0 ≤ m ≤ n(n-1)/2, which represent, respectivelly, the number of points on the alternative network and the number of pairs of points for which the interference probabilities were measured. On the m following lines, are given (in each line) two integers 1 ≤ u,v ≤ n and a rational 0 ≤ puv ≤ 1 representing that between two points u and v, the probability of interference is puv. A value n = 0 indicates the end of the instances and must not be processed. You can assume that it's always possible to satisfy the restriction (i).
For each solved instance, you must print an identifier Instancia h, where h is an integer number, sequential and growing from 1. On the next line, you must print (with five decimal places) the minimum probability of interference calculated for the instance. A blank line must separate each instance's output.
| Sample Input | Sample Output |
|
5 8 |
Instancia 1 |