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. Đồ thị có thể có cạnh lặp (nhiều cạnh nối cùng một cặp đỉnh) và khuyên (cạnh nối một đỉnh với chính nó).

Hai cây khung được coi là khác nhau nếu tập cạnh được chọn khác nhau (hai cạnh lặp nối cùng một cặp đỉnh vẫn là hai cạnh khác nhau).

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$ là 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 (giá trị thật, không lấy modulo) 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 A_i,B_i\le N$
• $1\le W_i\le {10}^6$
• Mỗi giá trị trọng số xuất hiện tối đa 3 lần

Ví dụ