問題文

ダイナミック王国には $N$ 個の村があり、$0$ から $N-1$ までの番号がついています。それらの村は $M$ 本の道でひと繋がりになっていました。「ひと繋がりになっている」とは、どの村からどの村へもいくつかの道を辿って行くことが出来る状態のことを指します。ある日大規模な災害によって全ての道が壊れて、村と村の間の移動が出来なくなってしまいました。あなたは王様の高橋君から、道を修理してダイナミック王国の $N$ 個の村をひと繋がりにする仕事を依頼されました。

あなたはまず、それぞれの道を修理するため必要な費用と時間を見積もりました。そして、修理する道を適切に選んだ時の「採算がとれる最低限の時給」の最小値を計算することにしました。「採算がとれる最低限の時給」とは、「道を修理するためにかかる時間の合計」×「時給」が「道を修理するためにかかる費用の合計」と等しくなる時の「時給」の金額の値を指します。

必ずしも全ての道を修理する必要はないことや、村をひと繋がりにするために必要のない道を修理しても良いことに注意して下さい。

入力例1

3 2
0 1 5 3
1 2 5 2

3 2
0 1 5 3
1 2 5 2

出力例1

2

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

3 3
0 1 1 1
1 2 3 1
2 0 2 1

出力例2

1.500

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

4 4
0 1 1 1
1 2 1 1
2 0 1 1
0 3 5 3

出力例3

1.3333333

1.3333333

このケースでは、全ての道を修理するときに「採算がとれる最低限の時給」が $1.333...$ となり、最小となります。