P1768 Heavenly Road

"That is a magical Sky Road, sending the first shen niu (pinyin) to heaven," Mr. XDM sang this "friendly" song, and a mischievous problem idea appeared in his mind. After discussing with the master C_SUNSHINE, this mischievous problem finally appeared in this exam, aiming to stump a bunch of OIers whose brains are not flexible enough (JOHNKRAM, this is really not about you...).

Back to the point. In Xiao X’s dream, he opened a large travel company in Tibet. Now he needs to design a set of railway lines connecting various scenic spots in Tibet. However, Xiao X found that tourists are very picky. They take trains to travel between scenic spots. The spots themselves are surely fun, but what really matters is the journey. Imagine taking a train around in a loop only to find yourself back at a spot you have already visited. You spend a lot of money and still cannot see good scenery along the way. That would be very frustrating. Therefore, Xiao X assigns two values to every route, $V_i$ and $P_i$, representing the scenery fun value of the train line and the price for one ride, respectively. Now Xiao X wants to know the maximum value of the ratio between the sum of $V$ and the sum of $P$ over any cycle that a passenger can take starting from any scenic spot. This is to recommend a circular tour route for customers (the route does not have to include all scenic spots, but no railway route may be repeated). Then, Xiao X woke up and came to you...

The first line contains two positive integers $N,M$, indicating there are $N$ scenic spots and $M$ railway routes. The railway routes are directed. Each of the following $M$ lines contains $4$ positive integers, representing the start point, end point, $V$ value, and $P$ value of a route. Note that there may be multiple tracks between two vertices, but you can take only one of them at a time.

Output a real number, the maximum ratio on a cycle, keeping $1$ decimal place. If there is no cycle, output $-1$.

For $30\%$ of the testdata, $1 \le N \le 100$, $1 \le M \le 20$. For $60\%$ of the testdata, $1 \le N \le 3{,}000$, $1 \le M \le 2{,}000$. For $100\%$ of the testdata, $1 \le N \le 7{,}000$, $1 \le M \le 20{,}000$, $1 \le V_i,P_i \le 1{,}000$. The answer is guaranteed to be within $200$.  Translated by ChatGPT 5