Cây Khung Nhỏ Nhất

Cho đồ thị vô hướng liên thông $N$ đỉnh, $M$ cạnh có trọng số. Mỗi giá trị trọng số xuất hiện tối đa 3 lần.

Hãy tìm:

1. Tổng trọng số của cây khung nhỏ nhất (MST).
2. Số lượng cây khung nhỏ nhất khác nhau (modulo ${10}^9+7$).

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$
• $M$ dòng tiếp theo: Ba số nguyên $A_i,B_i,W_i$ — cạnh nối $A_i$ với $B_i$ có trọng số $W_i$

Dữ liệu ra

• Một dòng chứa hai số: tổng trọng số MST và số MST khác nhau (mod ${10}^9+7$).

Ràng buộc

• $1\le N\le 40000$
• $1\le M\le 100000$
• $1\le W_i\le {10}^6$

Ví dụ