AT_abc324_f [ABC324F] Beautiful Path

[problemUrl]: https://atcoder.jp/contests/abc324/tasks/abc324_f $ N $ 個の頂点と $ M $ 本の辺からなる有向グラフがあります。各辺には**美しさ**と**コスト**の $ 2 $ つの正整数値が定められています。 $ i\ =\ 1,\ 2,\ \ldots,\ M $ について、$ i $ 番目の辺は頂点 $ u_i $ から頂点 $ v_i $ への有向辺であり、その美しさは $ b_i $ 、コストは $ c_i $ です。 ここで、$ u_i\ \lt\ v_i $ が制約として保証されます。 頂点 $ 1 $ から頂点 $ N $ へのパス $ P $ を $ 1 $ つ選んだときの、下記の値としてあり得る最大値を求めてください。 - $ P $ 上のすべての辺の美しさの総和を、$ P $ 上のすべての辺のコストの総和で割った値 ここで、与えられるグラフにおいて頂点 $ 1 $ から頂点 $ N $ へのパスが $ 1 $ 個以上存在することが制約として保証されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ b_1 $ $ c_1 $ $ u_2 $ $ v_2 $ $ b_2 $ $ c_2 $ $ \vdots $ $ u_M $ $ v_M $ $ b_M $ $ c_M $

答えを出力せよ。出力された値と真の値の相対誤差もしくは絶対誤差が $ 10^{-9} $ 以下のとき、正答と判定される。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ u_i\ \lt\ v_i\ \leq\ N $ - $ 1\ \leq\ b_i,\ c_i\ \leq\ 10^4 $ - 頂点 $ 1 $ から頂点 $ N $ へのパスが存在する - 入力される値はすべて整数 ### Sample Explanation 1 パス $ P $ として、 $ 2,\ 6,\ 7 $ 番目の辺をこの順に通り頂点 $ 1\ \rightarrow\ 3\ \rightarrow\ 4\ \rightarrow\ 5 $ とたどるバスを選んだとき、「 $ P $ 上のすべての辺の美しさの総和を $ P $ 上のすべての辺のコストの総和で割った値」 は、 $ (b_2\ +\ b_6\ +\ b_7)\ /\ (c_2\ +\ c_6\ +\ c_7)\ =\ (9\ +\ 4\ +\ 2)\ /\ (5\ +\ 8\ +\ 7)\ =\ 15\ /\ 20\ =\ 0.75 $ であり、これがあり得る最大値です。