Nông dân John đang theo học một lớp thuật toán buổi tối tại trường đại học địa phương, và ông vừa học về cây khung nhỏ nhất. Tuy nhiên, giờ đây Nông dân John nhận ra rằng thiết kế trang trại của mình chưa hiệu quả như mong muốn và ông muốn đơn giản hóa bố cục trang trại.

Trang trại hiện được bố trí như một đồ thị, trong đó các đỉnh biểu diễn những cánh đồng và các cạnh biểu diễn những con đường giữa các cánh đồng, mỗi con đường có một độ dài tương ứng. Nông dân John nhận thấy rằng với mỗi giá trị độ dài, nhiều nhất ba con đường trong trang trại có cùng độ dài đó. FJ muốn loại bỏ một số con đường để trang trại trở thành một cây — tức là giữa mọi cặp cánh đồng chỉ có duy nhất một lộ trình. Hơn nữa, Nông dân John muốn cây này là một cây khung nhỏ nhất — một cây có tổng độ dài các cạnh nhỏ nhất có thể.

Hãy giúp Nông dân John tính không chỉ tổng độ dài các cạnh của một cây khung nhỏ nhất được tạo từ đồ thị trang trại, mà còn cả số cây khung nhỏ nhất khác nhau mà ông có thể tạo ra.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 40\,000\); \(1 \le M \le 100\,000\)), lần lượt biểu diễn số đỉnh và số cạnh trong đồ thị trang trại. Các đỉnh được đánh số từ \(1\) đến \(N\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\) và \(n_i\) (\(1 \le a_i,b_i \le N\); \(1 \le n_i \le 1\,000\,000\)), biểu diễn một cạnh nối đỉnh \(a_i\) với đỉnh \(b_i\) có độ dài \(n_i\). Không có độ dài cạnh \(n_i\) nào xuất hiện quá ba lần.

Dữ liệu ra

• Dòng đầu tiên chứa hai số nguyên biểu diễn độ dài của cây khung nhỏ nhất và số lượng cây khung nhỏ nhất (lấy modulo \(1\,000\,000\,007\)).

Ví dụ

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

4 3

Nguồn

USACO 2011 December Contest, Gold Division — Simplifying the Farm

Tác giả đề: Nathan Pinsker, 2011.