Counting Minimum Spanning Trees on a Farm Graph

Farmer John, an evening algorithms student, has recently learned about minimum spanning trees (MSTs). He now wishes to simplify his farm's layout by removing some pathways so that the farm becomes a tree (i.e. there is exactly one route between any two fields) and the sum of the lengths of the remaining pathways is minimized.

The farm is represented as an undirected weighted graph. The vertices denote the fields, and the edges denote the pathways between fields, each having an associated length. An important constraint is that for each distinct length, there are at most three pathways with that length.

Your task is to help Farmer John by computing both:

• the total edge length of a minimum spanning tree
• the number of different possible minimum spanning trees that can be formed.

If there are multiple ways to form an MST with the same total edge length, you must count all those distinct ways. Any formulas in your explanation should use LaTeX; for instance, the number of edges in a spanning tree of a connected graph with $n$ vertices is $n-1$.

inputFormat

The input begins with two integers $n$ and $m$ ($2 \le n \le 10^5$, $n-1 \le m \le 10^5$), representing the number of fields and pathways, respectively.

Each of the next $m$ lines contains three integers $u$, $v$, and $w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$) indicating that there is a pathway between fields $u$ and $v$ with length $w$. It is guaranteed that for any particular weight $w$, there are at most three edges with that weight.

outputFormat

Output two space‐separated integers on a single line: the first is the total length of the minimum spanning tree and the second is the number of distinct minimum spanning trees that can be formed.

sample

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

4 3