Đất nước của ~w~ có ~V~ thành phố và ~E~ tuyến đường một chiều nối giữa các thành phố này. ~w~ đang ở thành phố ~1~ và muốn di chuyển tới thành phố ~V~ với vận tốc trung bình bé nhất có thể.

Bạn được cho biết thông tin về các con đường này: mỗi con đường sẽ được cho dưới dạng ~u~ ~v~ ~s~ t, trong đó ~u~ là điểm đầu, ~v~ là điểm cuối, ~s~ là độ dài con đường và ~t~ là thời gian cần để đi qua con đường đó (bạn không được đi chậm hơn vì sẽ gây cản trở tới giao thông trên các tuyến đường). Hãy giúp ~w~ tìm ra con đường có vận tốc trung bình bé nhất nhé!

Input

Dòng đầu tiên chứa ~2~ số ~V~ và ~E~.

~E~ dòng tiếp theo mỗi dòng chứa ~4~ số nguyên dương ~u~ ~v~ ~s~ t.

Output

• Một số thực duy nhất là kết quả bài toán, in ra 6 chữ số sau dấu phẩy. Nếu không tồn tại đường đi in ra -1.

Giới hạn

• ~V \leq 500~, ~E \leq 10^{4}~.
• ~s~, ~t \leq 10^{8}~
• Trong 50% số test: ~V \leq 100~, ~E \leq 1000~. ~s~, ~t \leq 100~.

Sample Input

4 4
1 2 2 1
1 3 3 2
2 4 5 3
3 4 5 4

Sample Output

1.333333314