Đầu năm 2022, người ta thành lập một dự án xây dựng một thành phố trên biển để đến đầu năm 2028 con người có thể sống và sinh hoạt ở đó. Giả sử rằng trong năm 2028, phương tiện giao thông chủ yếu sẽ là các phương tiện giao thông công cộng nên để đi lại giữa hai điểm bất kỳ trong thành phố người ta có thể yên tâm chọn đường đi ngắn nhất mà không sợ bị trễ giờ do kẹt xe. Khi mô hình thành phố được thiết kế xong, người ta đưa cho các chuyên gia thẩm định dự án để đóng góp ý kiến trước khi xây dựng thành phố, các ý kiến đều cho rằng hệ thống đường phố như vậy là quá nhiều, làm tăng chi phí xây dựng cũng như bảo trì thành phố.

Yêu cầu: Bạn hãy bỏ đi một số đường trong dự án xây dựng thành phố thỏa mãn:

• Nếu giữa hai địa điểm bất kỳ trong dự án ban đầu có ít nhất một đường đi thì sự sửa đổi này không làm ảnh hưởng tới độ dài đường đi ngắn nhất giữa hai địa điểm đó;

• Tổng độ dài của những con đường được giữ lại là nhỏ nhất.

Dữ liệu vào:

• Dòng thứ nhất ghi hai số nguyên dương là số địa điểm \(n\) và số đường phố \(m\) (giữa hai địa điểm bất kỳ có nhiều nhất là một con đường nối chúng; \(1 < n \leq 200,\ 1 < m \leq 19000\))

• \(m\) dòng tiếp theo, mỗi dòng ghi ba số nguyên dương \(u,\ v,\ c\) cho biết có đường hai chiều nối giữa hai địa điểm \(u,\ v\) và độ dài của con đường đó là \(c\ (1 < \ c \leq 10000)\)

Kết quả ra: Xuất ra màn hình hai số nguyên dương \(k\) và \(d\) trong đó \(k\) là tổng số con đường được giữ lại và \(d\) là tổng độ dài các con đường này thỏa mãn theo các yêu cầu trên.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Ví dụ:

Giải thích: