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
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