406206: GYM102309 H Horton and Orz Pandas

Horton is a famous swimmer, just like Cai Xukun is a famous basketball player. He swims slowly but he can make rumours as fast as Hong Kong journalists.

Now Horton is making fake news about Orz Pandas. To respond the fake news quickly, the Orz Pandas assembled a team containing $$$n$$$ Orz Pandas. It will cost $$$a_i$$$ dollar to build a data link between the $$$x_i$$$-th and the $$$y_i$$$-th Orz Pandas with a reliability of $$$b_i$$$.

The Orz Pandas want to build some data links so that each Orz Panda can communicate with all Orz Pandas in the responding team through a path of data links. If there are multiple ways to choose the data links to be built, the Orz Pandas wants to choose a subset $$$S$$$ of all possible data links to maximize

$$$$$$f(S) = \frac{\sum_{(x_i, y_i) \in S} b_i}{\sum_{(x_i, y_i) \in S} a_i}$$$$$$

Can you help the Orz Pandas to find the maximized $$$f(S)$$$?

There are multiple test cases. Please process until EOF.

For each test case, the first line contains two integers $$$n$$$, $$$m$$$. The $$$i-th$$$ line of the next $$$m$$$ lines contains $$$4$$$ integers $$$x_i$$$, $$$y_i$$$, $$$a_i$$$, and $$$b_i$$$, representing a possible data link.

It's guaranteed that $$$1 \leq x_i, y_i \leq n \leq 10^4$$$, $$$n > 1$$$, $$$1 \leq m \leq 10^5$$$, $$$1 \leq a_i, b_i \leq 10^7$$$, and it's possible to build some data links so that each Orz Panda can communicate with all Orz Pandas in the team through a path of data links.

For each test case, output one line containing the maximized $$$f(S)$$$. Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.

4 4
1 2 20 10
2 3 30 10
3 4 40 10
4 1 50 10

0.3333333333