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\).

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ờ\)).

Ràng buộc