/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ダイナミック王国には N 個の村があり、0 から N-1 までの番号がついています。それらの村は M 本の道でひと繋がりになっていました。「ひと繋がりになっている」とは、どの村からどの村へもいくつかの道を辿って行くことが出来る状態のことを指します。ある日大規模な災害によって全ての道が壊れて、村と村の間の移動が出来なくなってしまいました。あなたは王様の高橋君から、道を修理してダイナミック王国の N 個の村をひと繋がりにする仕事を依頼されました。
あなたはまず、それぞれの道を修理するため必要な費用と時間を見積もりました。そして、修理する道を適切に選んだ時の「採算がとれる最低限の時給」の最小値を計算することにしました。「採算がとれる最低限の時給」とは、「道を修理するためにかかる時間の合計」×「時給」が「道を修理するためにかかる費用の合計」と等しくなる時の「時給」の金額の値を指します。
必ずしも全ての道を修理する必要はないことや、村をひと繋がりにするために必要のない道を修理しても良いことに注意して下さい。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 T_1 A_2 B_2 C_2 T_2 : A_M B_M C_M T_M
-
1 行目には、村の個数を表した整数 N (2 ≦ N ≦ 10^4) と、道の本数を表した整数 M (1 ≦ M ≦ 10^4) が空白区切りで与えられる。
-
続く M 行には、道の情報が与えられる。このうちの i 行目には 4 つの整数 A_i (0 ≦ A_i ≦ N-1), B_i (0 ≦ B_i ≦ N-1), C_i (1 ≦ C_i ≦ 10^6), T_i (1 ≦ T_i ≦ 10^6) が空白区切りで書かれており、これは 村 A_i と村 B_i を繋ぐ道があり、この道を修理するために費用が C_i、時間が T_i かかることを表している。
また、道の情報に関して以下の条件が成り立つとして良い。
- 全ての i について、A_i \neq B_i
- 全ての i, j (i \neq j) について、「A_i \neq A_j または B_i \neq B_j」かつ「A_i \neq B_j または B_i \neq A_j」
部分点
この問題には部分点が設定されている。
- M ≦ 16 を満たすテストケースすべてに正解した場合は 20 点が与えられる。
出力
「採算がとれる最低限の時給」の最小値を 1 行に出力せよ。
出力は絶対誤差が 10^{-2} 以下であれば許容される。
なお、出力の末尾には改行をいれること。
入力例1
3 2 0 1 5 3 1 2 5 2
出力例1
2
このケースでは、町をひと繋がりにするためには全ての道を修理しなければなりません。全ての道を修理するためにかかる費用の合計が 10 で時間の合計が 5 であるため、採算がとれる最低限の時給は 2 となります。
誤差は 10^{-2} まで許容されるため、2.01 や 1.99 などと出力しても正解となります。
入力例2
3 3 0 1 1 1 1 2 3 1 2 0 2 1
出力例2
1.500
このケースでは、1 つ目の道と 3 つ目の道を修理するときに「採算がとれる最低限の時給」が 1.5 となり、最小となります。
入力例3
4 4 0 1 1 1 1 2 1 1 2 0 1 1 0 3 5 3
出力例3
1.3333333
このケースでは、全ての道を修理するときに「採算がとれる最低限の時給」が 1.333... となり、最小となります。