Problem Statement

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

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

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

Input

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

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$ 点が与えられる。

Output

「採算がとれる最低限の時給」の最小値を $1$ 行に出力せよ。

出力は絶対誤差が $10^{-2}$ 以下であれば許容される。

なお、出力の末尾には改行をいれること。