Đầu năm 2022, người ta thành lập một dự án xây dựng thành phố trên biển để đến dầu 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 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 ~2~ số nguyên 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 một con đường nối chúng)
• ~M~ dòng tiếp theo, mỗi dòng ghi ~3~ số nguyên ~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~.

Kết quả ra

• Xuất ra màn hình hai số nguyên ~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.

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

Giới hạn

• ~1 \le N \le 200, 1 \le M \le 19000~.
• ~1 \le c \le 10000~.

Ví dụ

Dữ liệu vào

5 6
1 2 2
1 3 1
2 3 5
2 5 7
3 4 2
4 5 1

Kết quả ra

4 6

Giải thích

• Bỏ đi các con đường nối địa điểm ~2~ và địa điểm ~3~, đường nối địa điểm ~2~ và địa điểm ~5~. Số các con đường còn lại là ~4~ và tổng độ dài là ~1 + 2 + 2 + 1 = 6~.