「Nhk R2」Ustesiar
题号：NC259919
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

给定一张 n 个点的有向图 G，每一条边带两个权值 a_i, b_i，要求选出任意多个环，使得每个点恰好处于一个环上，令选出环上的边组成的边集为 E，最大化 \frac{\sum_{i \in E}a_i}{\sum_{i \in E}b_i}。答案的允许误差为 10^{-4}。题目保证有解，且无重边、自环。

输入描述:

第一行两个整数 n, m。
接下来的 m 行，每行 4 个整数 u_i, v_i, a_i, b_i，表示一条从 u_i 到 v_i 的边权值为 a_i, b_i 的有向边。

输出描述:

输出一个实数，表示 \large\frac{\sum_{i \in E} a_i }{\sum_{i \in E} b_i } 的最大值。
示例1

输入

复制 
3 4
1 2 40 3
2 3 80 2
3 1 50 40
3 2 20 1

输出

复制 
3.777778
示例2

输入

复制 
6 9
1 2 6 4
2 3 8 1
3 4 3 2
4 5 9 6
5 6 1 1
6 1 2 1
6 4 1 1
3 1 6 2
5 3 3 1

输出

复制 
2.066666

备注:

对于所有的数据 n \le 300, m \le 1000，1\leqslant u, v\leqslant n，1\leqslant a_i, b_i\leqslant 2^{30}，所有的运算结果均在 2^{30} 以内。