Mirko và Slavko là hai thí sinh duy nhất tại Grand Prix of Dabrovina Donja được lái qua những ngôi làng gần đó. Các ngôi làng được kết nối bằng đường một chiều và với mỗi con đường chúng ta biết ~M_i~ và ~S_i~ , thời gian cần thiết để Mirko và Slavko đi qua con đường đó. Bản thân cuộc đua là vòng tròn (có nghĩa là nó bắt đầu và bắt đầu ở cùng một ngôi làng), nhưng bản thân lộ trình vẫn chưa được xác định.

Mirko đã hối lộ ban tổ chức cuộc đua để họ chọn con đường có lợi cho anh. Cụ thể, ban tổ chức sẽ chọn tuyến đường ngắn nhất (có số lượng đường tối thiểu) sao cho Mirko nhanh hơn Slavko trên tuyến đường đó. Nếu tình cờ có một số tuyến đường như vậy, ban tổ chức sẽ chọn tuyến đường mà Mirko có được lợi thế tối đa.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, M~ ~(2 \le N \le 300, 2 \le M \le N(N-1))~, số thôn và số đường nối.
• Mỗi ~M~ dòng tiếp theo chứa ~4~ số nguyên ~A_i, B_i , M_i , S_i~ ~(1 ≤ A_i , B_i ≤ N, Ai ≠ Bi, 0 ≤ S_i, M_i ≤ 10^6)~. Tương ứng là ngôi làng đầu tiên và cuối cùng của con đường thứ ~i~, thời gian cần thiết để Mirko và thời gian cần thiết để Slavko băng qua con đường đó. Sẽ không tồn tại hai con đường khác nhau nối cùng một cặp làng theo cùng một hướng.

Output

• Dòng đầu ra đầu tiên và duy nhất phải chứa hai số nguyên: tuyến đường ngắn nhất có thể (với số lượng đường tối thiểu) sao cho Mirko thắng và lợi thế tối đa mà Mirko có thể đạt được trên tuyến đường có độ dài ngắn nhất.

Xin lưu ý: Dữ liệu đầu vào sẽ luôn tồn tại một tuyến đường đáp ứng các điều kiện từ văn bản.

Sample Input 1

3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 4

Sample Output 1

2 1

Sample Input 2

5 7
1 2 4 1
2 3 5 1
3 1 1 6
1 3 15 5
2 4 7 5
4 5 1 4
5 3 1 0

Sample Output 2

5 2