ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Portkey Network

Time limit: 4.0 second
Memory limit: 64 MB
A Muggle firm offered Lucius Malfoy a contract for laying a portkey network connecting the firm's branches. Muggles believe that the cost of creating a portkey is proportional to the distance over which this portkey can transfer a person, so they're ready to pay for each meter of the network. Their requirements are the following: the network must make it possible for employees to travel from any branch of the firm to any other branch (using several portkeys if necessary), and there mustn't be redundant portkeys (such that can be excluded and the network would still connect all the branches).
Lucius understands that the cost of a portkey is determined not by the distance, but by some other factors. He wants to cheat the Muggles and lay a network for which the ratio of the total cost of portkeys to the amount of money paid by the Muggles is minimal. Thus, he tries to minimize the mean cost of one meter of the network. Help Mr. Malfoy to cheat the Muggles.


The first line contains the number of the firm's branches N (1 ≤ N ≤ 1000). The second line contains an integer M (1 ≤ M ≤ 500000), which is the number of pairs of branches that can technically be connected by a portkey. The next M lines describe these pairs: in each of these lines, the numbers of the branches, the distance between them in meters, and the cost of creating a portkey are given. The numbers in each line are separated with spaces. Costs and distances are integers in the range from 1 to 106. You may assume that a network satisfying the firm's requirements always exists.


Output the minimal mean cost of one meter of the network accurate to 10−8. The mean cost of one meter is the ratio of the total cost of the network's portkeys to its total length.


1 2 50 60
1 3 100 100
2 3 100 100
1 2 1000 3000
1 3 1 5
2 3 1000 1997
Problem Author: Author — Den Raskovalov, text by Stanislav Vasilyev
Problem Source: The Xth Urals Collegiate Programing Championship, March 24-25, 2006
To submit the solution for this problem go to the Problem set: 1447. Portkey Network