Putata và Budada đang chơi một trò chơi mới. Trong trò chơi này, Putata cố gắng di chuyển tới đích của mình và Budada cố gắng đưa Putata trở lại điểm xuất phát.

Có một đồ thị gồm $n$ đỉnh và $m$ cạnh có hướng. Putata sẽ bắt đầu từ đỉnh $1$ và đích của cậu là đỉnh $n$. Putata có hai cách để đi qua mỗi cạnh. Cách đầu tiên là đi bộ qua cạnh và sẽ mất $t_i$ giây, nhưng cậu sẽ có xác suất $\frac{p_i}{100}$ bị Budada phát hiện. Nếu Budada phát hiện Putata trên một cạnh nào đó, hắn sẽ dịch chuyển Putata về đỉnh $1$ sau khi Putata đi hết cạnh hiện tại. Cách thứ hai là lén qua cạnh, sẽ mất $c_i$ giây. Bằng cách lén qua cạnh, Putata sẽ không bị Budada phát hiện trên cạnh này.

Hãy giúp Putata tính thời gian kỳ vọng nhỏ nhất để di chuyển tới đỉnh $n$ dưới chiến lược tối ưu của cậu.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n,m$ ($1 \leq n,m \leq 10^5$), lần lượt là số đỉnh và số cạnh của đồ thị.

Mỗi dòng trong $m$ dòng tiếp theo chứa năm số nguyên $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$), biểu diễn một cạnh có hướng từ $u_i$ đến $v_i$.

Dữ liệu ra

In ra một số thực, là thời gian kỳ vọng nhỏ nhất để Putata di chuyển tới đỉnh $n$ dưới chiến lược tối ưu của cậu. Nếu Putata không thể đi từ $1$ tới $n$, in ra $-1$.

Câu trả lời của bạn sẽ được coi là đúng nếu sai số tương đối hoặc tuyệt đối của nó nhỏ hơn $10^{-6}$. Chính xác, gọi đáp án của bạn là $a$ và đáp án của ban giám khảo là $b$. Câu trả lời của bạn sẽ được coi là đúng nếu $\frac{|a-b|}{\max(1,|b|)}\leq 10^{-6}$.

Ví dụ

Đầu vào 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

Đầu ra 1

12.5000000000

Đầu vào 2

2 1
2 1 99 99 0

Đầu ra 2

-1