Trong chiến dịch khám phá bề mặt của mặt trăng, một nhóm các nhà khoa học đã phát hiện \(n\) địa điểm có trữ lượng khoáng sản cao, các địa điểm này được đánh số thứ tự \(1\) đến \(n\). Hiện tại, các nhà khoa học đang lên kế hoạch để khai thác lượng khoáng sản tại \(n\) địa điểm này. Kế hoạch được đặt ra như sau:

• Đầu tiên, các nhà khoa học sẽ thiết lập các con đường kết nối các địa điểm này lại với nhau. Bằng một số nghiên cứu, các nhà khoa học đã tìm ra được \(m\) con đường hai chiều có thể được xây dựng, mỗi con đường kết nối hai địa điểm với nhau. Các con đường được đánh số từ \(1\) đến \(m\), chi phí để xây dựng và độ dài con đường thứ \(i\) nối từ địa điểm \(u_i\) đến địa điểm \(v_i\) lần lượt là \(c_{u_i v_i}\) và \(d_{u_i v_i}\). Chi phí xây dựng các con đường được tính toán tuần tự, nghĩa là chi phí xây dựng con đường thứ \(i\) được tính toán ở thời điểm trước thời điểm tính toán chi phí cho con đường thứ \(i+1\). Hiển nhiên, để tiết kiệm chi phí thì hệ thống các con đường được xây dựng cần đảm bảo sao cho tổng chi phí là nhỏ nhất. Tuy nhiên, ngoài vấn đề chi phí thì vấn đề thời gian lại được các nhà khoa học quan tâm nhiều hơn. Do đó, họ đã chọn kế hoạch xây dựng các con đường như sau:
• Nếu vào thời điểm tính toán được chi phí xây dựng con đường nối từ địa điểm \(u\) đến địa điểm \(v\) mà chưa có cách nào khác để đi từ \(u\) đến \(v\) thì họ sẽ cho tiến hành xây dựng con đường này, ngược lại họ sẽ không cho xây dựng đường này. Để đi từ \(u\) đến \(v\) có thể sử dụng một đường đi trực tiếp từ \(u\) sang \(v\) hoặc một đường đi gián tiếp từ \(u\) sang một số địa điểm trung gian và đến \(v\). Một con đường đi từ \(u\) sang \(v\) khi được bắt đầu xây dựng có nghĩa là sẽ có cách đi trực tiếp từ \(u\) đến \(v\).

• Hệ thống đường được xây dựng hoàn thiện khi giữa hai địa điểm bất kỳ luôn tìn được một cách di chuyển qua lại lẫn nhau.

• Tiếp theo, các nhà khoa học sẽ chọn ra hai địa điểm trong \(n\) địa điểm nay dùng để tập kết khoáng sản. Ở mỗi lượt thu gom, một thiết bị tự hành sẽ xuất phát từ một địa điểm và di chuyển đến điểm còn lại, trong quá trình di chuyển thiết bị tự hành sẽ tự tìm cách di chuyển qua tất cả các điểm để thu gom khoáng sản sao cho tổng khoảng cách di chuyển ngắn nhất.

Yêu cầu

• Hãy lập trình xác định tổng chi phí để xây dựng hệ thống đường theo mô tả trên và tổng khoảng cách ngắn nhất mà thiết bị tự hành phải di chuyển ở mỗi lượt thu gom nếu việc chọn hai điểm tập kết là tối ưu.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương \(n\) và \(m\)
• Dòng thứ \(i\) trong \(m\)m dòng tiếp theo ghi bốn số nguyên dương \(u_i, v_i, c_{u_i v_i}\) và \(d_{u_i v_i}\)

Ràng buộc

• \(3 \le n \le 10^5\)
• \(0 \le m \le 2 \times 10^5\)
• \(1 \le u_i, v_i \le n\)
• \(c_{u_i v_i}, d_{u_i v_i} \le 10^4\)
• Dữ liệu luôn đảm bảo có cách xây dựng hệ thống đường
• Giữa hai địa điểm có thể có nhiều hơn một đường đi trực tiếp.

Kết quả

• Hai số nguyên lần lượt là chi phí và khoảng cách tìm được.

Substask

• 40% số điểm tương ứng các test có \(n \le 10^2, m \le 10^3\)
• 60% số điểm còn lại không có ràng buộc gì khác

Input 1

4 6
1 2 2 3
4 2 3 1
1 4 1 1
2 3 2 2
1 3 1 2
3 4 3 4

Output 1

7 7

Giải thích 1

• Các con đường lần lượt được chọn để xây dựng hệ thống theo thứ tự là \(1,2,4\). Chi phí xây dựng là \(7\)
• Chọn điểm \(1\) và \(3\) làm hai điểm tập kết. Một cách di chuyển từ \(1\) đến \(3\) qua tất cả các điểm là \(1,2,4,2,3\). Tổng khoảng cách di chuyển là \(7\)

Input 2

5 10
1 2 2 3
4 2 3 1
1 4 3 5
2 3 2 2
2 4 1 5
4 1 2 3
1 3 1 2
3 4 3 4
5 4 4 1
4 5 4 1

Output 2

11 9