Gần đây người nông dân John đã quyết định mua một trang trại mới để mở rộng đế chế sữa của mình. Trang trại được kết nối với thị trấn gần đó bằng hệ thống các đường ống. John muốn tìm ra tập hợp các đường ống tối ưu nhất để bơm sữa từ trang trại tới thị trấn.

Một mạng lưới đường ống được biểu diễn bởi ~N~ giao điểm, đánh số từ ~1...N~. Giao điểm ~1~ là trang trại của John, còn giao điểm ~N~ là thị trấn. Có ~M~ đường ống hai chiều, mỗi đường ống kết nối hai giao điểm với nhau. Đường ống thứ ~i~ mất ~c_{i}~ chi phi để sử dụng và có lưu lượng là ~f_{i}~ lít sữa mỗi giây.

Nông dân John muốn tìm một con đường tối ưu nhất, điểm đầu là ~1~, điểm cuối là ~N~. Chi phí và lưu lượng của con đường lần lượt là tổng chi phí và lưu lượng nhỏ nhất của các đường ống mà nó đi qua. Nông dân John muốn tìm một con đường sao cho biểu thức lưu lượng chia chi phí là lớn nhất. Dữ liệu đảm bảo có một đường đi từ ~1~ đến ~N~.

Input

• Dòng đầu tiên ghi các số nguyên dương ~N~, ~M~ ~(2 \le N \le 1000, 1 \le M \le 1000)~.

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên dương ~a~, ~b~, ~c~, ~f~ thể hiện đường ống thứ ~i~ kết nối hai giao điểm ~a~ và ~b~, mất chi phí là ~c~ và có lưu lượng là ~f~ ~(1 \le c, f \le 1000)~.

Output

• Gọi giá trị của đường đi có lưu lượng chia chi phí lớn nhất là: ~S~. In ra ~\left \lfloor{S \times 10^6}\right \rfloor~ (làm tròn xuống).

Sample Input

3 2
2 1 2 4
2 3 5 3

Sample Output

428571

Giới hạn:

• Test 1 là test ví dụ.
• Các tests 2-5 thoả mãn ~1 \le N, M \le 100~.
• Các test còn lại có giới hạn gốc.

Note

• Giải thích: chỉ có một con đường từ ~1~ tới ~N~. Nó có lưu lượng là ~min(3, 4) = 3~ và chi phí là ~2 + 5 = 7~.