Putata と Budada は新しいゲームをしている。このゲームでは、Putata は自分の目的地へ移動しようとしており、Budada は Putata を出発点に戻そうとしている。

$n$ 頂点 $m$ 本の有向辺を持つグラフがある。Putata は頂点 $1$ から出発し、目的地は頂点 $n$ である。Putata は各辺を通過する方法を2つ持っている。1つ目の方法は辺を歩いて通過する方法であり、これには $t_i$ 秒かかるが、$\frac{p_i}{100}$ の確率で Budada に発見されてしまう。ある辺で Budada に Putata が発見された場合、Budada は Putata がその辺を通り終えた後に、Putata を頂点 $1$ にテレポートさせる。2つ目の方法は辺をこっそりと通過する方法であり、これには $c_i$ 秒かかる。こっそり通れば、この辺では Budada に発見されることはない。

Putata が最適な戦略のもとで頂点 $n$ に移動するまでの最小期待時間を計算するのを助けてほしい。

入力

最初の行には2つの整数 $n,m$ ($1 \leq n,m \leq 10^5$) が含まれ、グラフの頂点数と辺の数を表す。

続く $m$ 行のそれぞれには、5つの整数 $u_i, v_i, t_i, p_i, c_i$ ($1 \leq u_i,v_i \leq n$, $0 \leq t_i, c_i \leq 10^9$, $0 \leq p_i \leq 99$) が含まれ、頂点 $u_i$ から $v_i$ への有向辺を表す。

出力

実数を1つ出力せよ。これは、Putata が最適な戦略のもとで頂点 $n$ に移動するまでの最小期待時間を表す。Putata が頂点 $1$ から $n$ に到達できない場合は $-1$ を出力せよ。

答えは、絶対誤差または相対誤差が $10^{-6}$ 未満であれば正解とみなされる。形式的には、あなたの答えを $a$、審判の答えを $b$ とする。$\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$ が成り立てば正解とみなされる。

入出力例

入力例 1

4 6
1 2 1 60 10
2 4 9 50 10
2 3 0 99 5
3 2 1 0 10
3 4 3 60 5
1 1 4 51 4

出力例 1

12.5000000000

入力例 2

2 1
2 1 99 99 0

出力例 2

-1