Khu rừng Rùa và Thỏ sống có \(n\) vị trí được kết nối với nhau bằng \(m\) con đường 1 chiều. Trên con đường nối từ vị trí \(A_{i}\) đến vị trí \(B_{i}\), thời gian để Rùa đi hết con đường này là \(R_{i}\), thời gian để Thỏ đi hết con đường này là \(T_{i}\). Thời gian đi qua mỗi vị trí coi như không đáng kể.

Thỏ và Rùa đang lên kế hoạch chạy đua, đường đua sẽ là một chu trình xác định trước; cả hai cùng xuất phát tại một vị trí, chạy theo chu trình đó và trở về vị trí xuất phát; ai về đích trước là người chiến thắng.

Thỏ có ý định nhường Rùa nên muốn tìm một chu trình gồm ít con đường nhất, mà nếu chạy trên chu trình đó thì Rùa chắc chắn sẽ thắng Thỏ. Nếu có nhiều chu trình như vậy thì Thỏ muốn chọn chu trình mà chênh lệch thời gian về đích giữa Rùa và Thỏ là lớn nhất.

Hãy giúp Thỏ tìm một chu trình như mong muốn.

Dữ liệu vào:

Dòng đầu tiên chứa số hai nguyên dương \(n\) và \(m\).

Dòng thứ \(i\) trong m dòng tiếp theo chứa 4 số nguyên \(A_{i}\), \(B_{i}\), \(R_{i}\) và \(T_{i}\) cho biết có một con đường một chiều nối từ \(A_{i}\) đến \(B_{i}\) và thời gian để Rùa và Thỏ đi hết con đường đó lần lượt là \(R_{i}\) và \(T_{i}\).

Giữa hai vị trí \(A\) và \(B\) bất kỳ, có không quá 1 con đường nối theo chiều từ \(A\) đến \(B\), và có không quá 1 con đường nối theo chiều từ \(B\) đến \(A\).

Kết quả: Gồm 2 số trên một dòng được phân tách bởi một khoảng trắng: số đầu tiên là số con đường trong chu trình tìm được, số thứ hai là mức chênh lệch lớn nhất thời gian về đích giữa Rùa và Thỏ.

Giới hạn dữ liệu:

• \(2 \leq n,m \leq 300\).

• \(2 \leq m \leq n \times (n - 1)\).

• \(0 \leq R_{i},T_{i} \leq 10^{6}\).

Ví dụ

Ràng buộc:

• Có 40% điểm tương ứng với \(n \leq 20\).

• Có 60% điểm tương ứng với \(20 \leq n \leq 300.\)