Giải bài trực tuyến

  Đấ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 ≤ 500, E ≤ 10000.

  s,t ≤ 108.

  Trong 50% số test: V ≤ 100, E ≤ 1000. s,t ≤ 100.
 
Example
 
Input:
 
4 4
1 2 2 1
1 3 3 2
2 4 5 3
3 4 5 4
 
Output:
 
1.333333