409664: GYM103677 B With Grape Power comes Grape Responsibility

Catherine the Grape has an immense responsibility: to build power lines so that all of the citizens of Raisin Metropolis have guaranteed access to power. There are $$$n$$$ locations throughout the city that Catherine must ensure have power, numbered $$$1$$$ through $$$n$$$, with the power plant located at location $$$1$$$. A location has power if it is connected to the power plant via some sequence of power lines.

As part of her grape responsibility, Catherine must ensure that all citizens receive power without costing the city too much. The power company has offered Catherine $$$m$$$ quotes for power lines they might build, where the $$$i$$$th quote lists the cost $$$c_i$$$ to build a power line connecting locations $$$u_i$$$ and $$$v_i$$$. (Connecting two locations allows power to flow in either direction between them.)

The owner of the power company wants to help Catherine and offers her a coupon that allows her to swap the costs of any two quotes before building any power lines. Seeing that using the coupon can never increase the minimum cost of powering the city, Catherine agrees to the deal, and selects the two costs to swap and the set of power lines to build in a way that minimizes the overall total cost of connecting all locations to the power plant. She wonders, though, if there were other possible swaps that also would have yielded this same optimal cost?

Compute how many different quote swaps Catherine could have picked so that the optimal cost to connect power to the city is minimized. Two swaps are identical if they involve the same two quotes.

The power company guarantees that if Catherine chooses to build all of the power lines, then all $$$n$$$ locations will be connected to the power plant (though doing so is not necessarily the cheapest way to power the whole city).

The first line consists of two integers $$$n$$$ and $$$m$$$ $$$(3 \leq n \leq 100)$$$, $$$(n - 1 \leq m \leq 10^3)$$$, the number of city locations and number of power line quotes, respectively.

The next $$$m$$$ lines each consist of three integers $$$u_i$$$, $$$v_i$$$, and $$$c_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$, $$$(1 \leq c_i \leq 10^4)$$$, representing a quote to build a power line between locations $$$u_i$$$ and $$$v_i$$$ for cost $$$c_i$$$. No two quotes propose to connect the same pair of locations, nor does any quote offer to connect a location to itself.

Output the number of distinct quote pairs such that after swapping the prices of those two quotes, Catherine can provide power to all $$$n$$$ locations at the minimum price.

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

6

6 6
1 2 2
1 3 2
2 3 4
2 6 4
3 4 6
4 5 8

3

To power the city in the sample input, Catherine will have to build all of the quoted power lines regardless of which two costs she decides to swap. The use of the coupon will not change the sum of all of the quoted costs, so she can pick any two quotes and still achieve the optimal cost. The answer is thus $$$\binom{4}{2} = 6$$$.