Sau trận mưa lũ lớn, trung tâm cứu trợ đặt tại địa điểm số 1 cần vận chuyển hàng hóa đến khu vực bị cô lập nghiêm trọng nhất tại địa điểm số ~N~.

Hệ thống giao thông gồm ~N~ địa điểm được đánh số từ 1 đến ~N~ và ~M~ con đường hai chiều nối các địa điểm. Mỗi con đường nối hai địa điểm ~u, v~ có chi phí vận chuyển là ~c~ và giới hạn tải trọng tối đa là ~w~ (tấn).

Do điều kiện cầu đường không đồng đều, nếu một con đường trong hành trình chỉ chịu được ~w~ (tấn) thì xe chỉ có thể vận chuyển tối đa ~w~ (tấn) theo hành trình đó. Vì vậy, tải trọng của một hành trình được xác định bằng giá trị nhỏ nhất trong các giới hạn tải trọng của các con đường thuộc hành trình.

Xe cứu trợ chỉ chọn một hành trình duy nhất từ địa điểm 1 đến địa điểm ~N~. Hiệu quả của hành trình được xác định bởi: Hiệu quả = ~\frac{\text{Tải trọng của hành trình}}{\text{Tổng chi phí của hành trình}}~

Yêu cầu: Hãy xác định hiệu quả lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, M~ (~2 \le N \le 1000~; ~1 \le M \le 1000~);
• ~M~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương ~u, v, c, w~ (~u, v \le N~; ~u \ne v~; ~c, w \le 1000~). Dữ liệu đảm bảo tồn tại ít nhất một đường đi từ 1 đến ~N~.

Output

Ghi ra một số là ~10^6~ lần giá trị hiệu quả lớn nhất, lấy phần nguyên (tức là làm tròn xuống nếu giá trị này không phải số nguyên).

Sample Input 1

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

Sample Output 1

428571

• Nếu đi theo tuyến đường ~1 \rightarrow 2 \rightarrow 3~ thì tải trọng tối đa bằng ~\min(4, 3) = 3~ và tổng chi phí là ~2 + 5 = 7~, hiệu quả đạt được là ~\frac{3}{7}~.
• Nếu đi theo tuyến đường ~1 \rightarrow 3~ thì tải trọng tối đa bằng 2 và tổng chi phí bằng 15, hiệu quả đạt được là ~\frac{2}{15}~. Vậy hiệu quả lớn nhất là ~\frac{3}{7}~. Theo yêu cầu đề bài, kết quả là ~\lfloor 10^6 \times \frac{3}{7} \rfloor = 428571~.

Subtasks

• Có 30% số test ứng 30% số điểm của bài có ~2 \le N, M \le 100~ và mọi con đường có ~w~ bằng nhau;
• Có 30% số test ứng 30% số điểm của bài có ~2 \le N, M \le 100~;
• 40% số test còn lại ứng 40% số điểm của bài không có thêm ràng buộc.