Problem E: Tangled Cables

Problem

とある会社のネットワーク上には$n$台のコンピュータと、それらをつなぐ$m$本の通信ケーブルがある。コンピュータは$0$から$n - 1$までの識別子で区別され、通信ケーブルもまた$0$から$m - 1$までの識別子をもつ。

現在この会社にある任意の異なる2台のコンピュータは、いくつかの通信ケーブルを介して相互に通信することができるが、通信経路がただ一つに定まるとは限らない。

このネットワークには、通信ケーブルが多すぎて絡まってしまうという問題がある。そこであなたは、任意の通信について通信経路がただ一つになるようにいくつかの通信ケーブルを取り除くことにした。

通信ケーブル$i$はコンピュータ$a_i$と$b_i$を双方向につなぎ、その長さは$c_i$である。また、あなたが通信ケーブル$i$を取り除く際にかかる労力は$d_i$である。

作業を始める前に、あなたは取り除く通信ケーブルの長さの和に対する、作業を終えるまでにかかる労力の和の比を「おっくう感」とし、最小のおっくう感を見積もることにした。
ただし、一つも取り除けない場合のおっくう感は$0$である。

Input

入力は以下の形式で与えられる。

$n$ $m$
$a_1$ $b_1$ $c_1$ $d_1$
$a_2$ $b_2$ $c_2$ $d_2$
...
$a_m$ $b_m$ $c_m$ $d_m$

入力はすべて整数で与えられる。
1行目にはコンピュータの数$n$と通信ケーブルの数$m$が空白区切りで与えられる。
2行目以降の$m$行には、通信ケーブルの情報が空白区切りで与えられる。$i$番目の通信ケーブルの情報は、通信ケーブル$i$の情報を表す。

Constraints

入力は以下の条件を満たす。

• $2 \leq n \leq 10^4$
• $n-1 \leq m \leq min(\frac{n \times (n - 1)}{2}, 10^4)$
• $0 \leq a_i, b_i \leq n - 1 (a_i ≠ b_i)$
• $1 \leq c_i \leq 10^6$
• $0 \leq d_i \leq 10^6$

Output

おっくう感の最小値を実数で1行に出力する。ただし、$10^{-5}$を超える誤差を含んではならない。

Sample Input 1

4 5
0 2 22 13
0 3 15 25
1 2 3 3
1 3 28 5
2 3 5 22

Sample Output 1

0.36000

通信ケーブル$0$と通信ケーブル$3$を取り除くと、おっくう感は$(\frac{13 + 5}{22 + 28}) = 0.36$となり、これがおっくう感の最小値となる。

Sample Input 2

5 6
0 1 22 33
0 2 43 11
0 3 92 10
1 3 50 12
2 3 88 2
3 4 58 89

Sample Output 2

0.06667

Sample Input 3

2 1
0 1 1 1

Sample Output 3

0

Note

Link

 

---