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 10⁶. 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⁻⁸. The mean cost of one meter is the ratio of the total cost of the network's portkeys to its total length.