Farmer John theo học lớp thuật toán buổi tối ở đại học địa phương và vừa học cây khung nhỏ nhất. Ông nhận ra trang trại có thể được thiết kế hiệu quả hơn và muốn đơn giản hóa bố cục.

Trang trại là đồ thị: đỉnh là cánh đồng, cạnh là lối đi giữa chúng, mỗi lối có độ dài. Farmer John nhận thấy có tối đa ba lối cùng một độ dài. FJ muốn bỏ một số lối để thành cây, tức có duy nhất một đường đi giữa mọi cặp cánh đồng. Ông muốn cây khung nhỏ nhất, với tổng độ dài cạnh nhỏ nhất có thể.

Hãy giúp Farmer John tính cả tổng độ dài cây khung nhỏ nhất lẫn số cây khung nhỏ nhất khác nhau có thể tạo.

Dữ liệu vào

• Dòng $1$: hai số nguyên $N$, $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$, lần lượt là số đỉnh và cạnh. Đỉnh đánh số $1\ldots N$.
• Dòng $2\ldots M+1$: ba số nguyên $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$, mô tả cạnh từ $a_{i}$ đến $b_{i}$ dài $n_{i}$. Không độ dài $n_{i}$ nào xuất hiện quá ba lần.

Dữ liệu ra

• Dòng $1$: hai số nguyên, tổng độ dài cây khung nhỏ nhất và số cây như vậy modulo $1,000,000,007$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

4 3

Ghi chú

Chọn cả hai cạnh dài $1$ cùng bất kỳ cạnh dài $2$ cho cây khung nhỏ nhất dài $4$.

Tác giả bài toán: Nathan Pinsker, 2011