Counting Optimal Transportation Hub Upgrade Schemes

NJ City is rapidly developing thanks to its convenient transportation network. However, the surge of residents has put enormous pressure on its roads. To ease the congestion, the city plans to construct a new transportation hub by upgrading some of the existing two‐way roads into new, high-capacity roads.

The city consists of \(n\) districts, with some pairs connected by roads. Upgrading a road increases its capacity by a large factor, and each road has an associated upgrading cost. In the new hub, it is required that any two districts can connect using just the upgraded roads (directly or indirectly). The government wants to minimize the total upgrading cost. Since there might be multiple ways to achieve this minimum cost, two schemes are considered different if their sets of upgraded roads differ.

Formally, given an undirected graph with \(n\) vertices and \(m\) edges (each with cost \(c\)), you are to count the number of spanning trees with minimum total cost. In other words, compute the number of Minimum Spanning Trees (MSTs). If the graph is initially disconnected so that it is impossible to connect all districts, output \(0\).

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of districts and roads, respectively.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(c\), where \(u\) and \(v\) denote the districts (numbered from 1 to \(n\)) connected by a two-way road, and \(c\) is the upgrading cost for that road.

outputFormat

Output a single integer representing the number of optimal upgrade schemes (i.e. the number of Minimum Spanning Trees). If it is impossible to connect all districts, output \(0\).

sample

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

3