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

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.

Input

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

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.

Samples

inputoutput
3
3
1 2 50 60
1 3 100 100
2 3 100 100
1
3
3
1 2 1000 3000
1 3 1 5
2 3 1000 1997
2
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