Cứu trợ

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:

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

Input

Dữ liệu vào có cấu trúc như sau:

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

Ràng buộc:

• Có \(30\%\) số test ứng với \(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 với \(30\%\) số điểm của bài có \(2 \le N, M \le 100\);

• \(40\%\) số test còn lại ứng với \(40\%\) số điểm của bài không có thêm ràng buộc.

Output

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

Example

Input:

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

Output:

428571

Note

Nếu đi theo tuyến đường \(1 \to 2 \to 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 \to 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\).