Putata i Budada grają w nową grę. W tej grze Putata próbuje dotrzeć do celu, a Budada próbuje go zawrócić do punktu startowego.

Mamy graf składający się z $n$ wierzchołków i $m$ skierowanych krawędzi. Putata startuje z wierzchołka $1$, a jego celem jest wierzchołek $n$. Putata ma dwa sposoby na pokonanie każdej krawędzi. Pierwszym sposobem jest przejście przez krawędź, co zajmie mu $t_i$ sekund, ale z prawdopodobieństwem $\frac{p_i}{100}$ zostanie odkryty przez Budadę. Jeśli Budada odkryje Putatę na pewnej krawędzi, to po przejściu przez tę krawędź przenosi go teleportacyjnie do wierzchołka $1$. Drugim sposobem jest prześlizgnięcie się przez krawędź, co zajmie Putacie $c_i$ sekund. Prześlizgując się, Putata nie zostanie odkryty przez Budadę na tej krawędzi.

Pomóż Putacie obliczyć minimalny oczekiwany czas dotarcia do wierzchołka $n$ przy jego optymalnej strategii.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n,m$ ($1 \leq n,m \leq 10^5$), oznaczające liczbę wierzchołków i liczbę krawędzi w grafie.

Każdy z kolejnych $m$ wierszy zawiera pięć liczb całkowitych $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$), oznaczających skierowaną krawędź z $u_i$ do $v_i$.

Wyjście

Wypisz liczbę rzeczywistą, oznaczającą minimalny oczekiwany czas dotarcia Putaty do wierzchołka $n$ przy jego optymalnej strategii. Jeśli dotarcie z $1$ do $n$ jest niemożliwe, wypisz $-1$.

Twoja odpowiedź zostanie uznana za poprawną, jeśli jej błąd względny lub bezwzględny jest mniejszy niż $10^{-6}$. Formalnie, niech Twoja odpowiedź wynosi $a$, a odpowiedź jury wynosi $b$. Twoja odpowiedź będzie uznana za poprawną, jeśli $\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$.

Przykład

Wejście 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

Wyjście 1

12.5000000000

Wejście 2

2 1
2 1 99 99 0

Wyjście 2

-1