Putata et Budada jouent à un nouveau jeu. Dans ce jeu, Putata essaie de se rendre à sa destination et Budada essaie de le renvoyer à son point de départ.

Il y a un graphe avec $n$ sommets et $m$ arêtes orientées. Putata commence au sommet $1$ et sa destination est le sommet $n$. Putata a deux façons de parcourir chaque arête. La première façon est de traverser l'arête à pied ; cela prendra $t_i$ secondes, mais il y a une probabilité $\frac{p_i}{100}$ qu'il soit découvert par Budada. Si Budada découvre Putata sur une arête, il téléportera Putata au sommet $1$ après que Putata ait traversé l'arête en cours. La deuxième façon est de se faufiler le long de l'arête, ce qui prendra $c_i$ secondes. En se faufilant, Putata ne sera pas découvert par Budada sur cette arête.

Aidez Putata à calculer le temps espéré minimal pour atteindre le sommet $n$ selon sa meilleure stratégie.

Entrée

La première ligne contient deux entiers $n, m$ ($1 \leq n,m \leq 10^5$), indiquant le nombre de sommets et le nombre d'arêtes du graphe.

Chacune des $m$ lignes suivantes contient cinq entiers $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$), indiquant une arête orientée de $u_i$ vers $v_i$.

Sortie

Affichez un nombre réel, le temps espéré minimal pour que Putata atteigne le sommet $n$ selon sa meilleure stratégie. S'il est impossible pour Putata d'aller de $1$ à $n$, affichez $-1$.

Votre réponse sera considérée correcte si son erreur relative ou absolue est inférieure à $10^{-6}$. Formellement, soit $a$ votre réponse et $b$ la réponse du jury. Votre réponse sera considérée correcte si $\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$.

Exemples

Entrée 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

Sortie 1

12.5000000000

Entrée 2

2 1
2 1 99 99 0

Sortie 2

-1