Description

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

Input Format

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 Format

Output a real number, the maximum ratio on a cycle, keeping $1$ decimal place.

If there is no cycle, output $-1$.

5 6
1 2 1 1
4 1 6 2
5 4 8 1
2 3 2 2
5 2 4 1
3 5 6 4

2.3

Hint

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