Quốc gia của Tèo có mạng lưới giao thông gồm \(N\) thành phố và \(M\) con đường hai chiều liên kết. Mỗi con đường thứ \(i\) có độ dài địa lý là \(L\) kilomet và tốc độ tối đa quy định là \(V\) km/h. Thời gian di chuyển của xe trên con đường này bằng \(L / V\) giờ.

Hãy giúp Tèo tìm lộ trình tốn ít thời gian di chuyển nhất đi từ thành phố \(1\) đến thành phố \(N\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(u, v, L, V\) (\(1 \le u, v \le N\), \(1 \le L \le 1000\), \(1 \le V \le 100\)) mô tả con đường nối \(u\) và \(v\) có chiều dài \(L\) km và vận tốc \(V\) km/h.

Định dạng đầu ra

• Một số thực duy nhất làm tròn đến 3 chữ số thập phân là thời gian di chuyển tối thiểu tính bằng giờ. Nếu không thể đi tới, in ra \(-1.000\).

Ràng buộc

Ví dụ

Input:

3 3
1 2 100 50
2 3 60 60
1 3 200 80

Output:

2.500

(Giải thích ví dụ: Đi 1 -> 3 trực tiếp tốn 200/80 = 2.5 giờ. Đi 1 -> 2 -> 3 tốn 100/50 + 60/60 = 2 + 1 = 3 giờ. Lộ trình tối ưu là 2.500 giờ).