CF1108F.MST Unification

You are given an undirected weighted connected graph with $n$ vertices and $m$ edges without loops and multiple edges.

The $i$-th edge is $e_i = (u_i, v_i, w_i)$; the distance between vertices $u_i$ and $v_i$ along the edge $e_i$ is $w_i$ ($1 \le w_i$). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph.

A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges).

You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by $1$. You can increase the weight of each edge multiple (possibly, zero) times.

Suppose that the initial MST cost is $k$. Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains $k$, but MST is unique (it means that there is only one way to choose MST in the obtained graph).

Your problem is to calculate the minimum number of operations required to do it.

给你一个包含 $n$ 个顶点和 $m$ 条边的无向带权连通图，图中不含自环和重边。

第 $i$ 条边为 $e_i = (u_i, v_i, w_i)$；沿边 $e_i$ 连接顶点 $u_i$ 和 $v_i$ 的距离为 $w_i$（其中 $1 \le w_i$）。该图是连通的，即对任意一对顶点，均存在一条仅由图中边构成的路径连接它们。

在边权均为正数的情况下，最小生成树（MST） 是原图边集的一个子集，它连接所有顶点，且在所有满足该性质的子集中总权重（即所选边的权重之和）最小。

你可以对给定图进行修改。唯一允许的操作是：将某条边的权重增加 $1$。每条边可执行该操作任意多次（包括零次）。

假设初始图的 MST 总权重为 $k$。你的任务是：以最少的操作次数，增加若干条边的权重，使得所得图的 MST 总权重仍为 $k$，但 MST 唯一（即所得图中仅存在唯一一种选择 MST 的方式）。

你需要计算完成该目标所需的最少操作次数。

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5$) — the number of vertices and the number of edges in the initial graph.

The next $m$ lines contain three integers each. The $i$-th line contains the description of the $i$-th edge $e_i$. It is denoted by three integers $u_i, v_i$ and $w_i$ ($1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le w \le 10^9$), where $u_i$ and $v_i$ are vertices connected by the $i$-th edge and $w_i$ is the weight of this edge.

It is guaranteed that the given graph doesn't contain loops and multiple edges (i.e. for each $i$ from $1$ to $m$ $u_i \ne v_i$ and for each unordered pair of vertices $(u, v)$ there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$n - 1 \le m \le 2 \cdot 10^5$），分别表示初始图中的顶点数和边数。

接下来的 $m$ 行每行包含三个整数。第 $i$ 行描述第 $i$ 条边 $e_i$，由三个整数 $u_i, v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$，$1 \le w_i \le 10^9$）组成，其中 $u_i$ 和 $v_i$ 是第 $i$ 条边所连接的两个顶点，$w_i$ 是该边的权重。

保证给定图中不含自环和重边（即对每个 $i$（$1 \le i \le m$）均有 $u_i \ne v_i$，且对任意无序顶点对 $(u, v)$，至多存在一条边连接该对顶点）。同时保证给定图是连通的。

Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.

输出一个整数——在不改变初始图的最小生成树（MST）代价的前提下，使该图的 MST 唯一所需的最少操作次数。

The picture corresponding to the first example:

You can, for example, increase weight of the edge $(1, 6)$ or $(6, 3)$ by $1$ to unify MST.

The picture corresponding to the last example:

You can, for example, increase weights of edges $(1, 5)$ and $(2, 4)$ by $1$ to unify MST.

第一个示例对应的图片：

例如，你可以将边 $(1, 6)$ 或 $(6, 3)$ 的权值增加 $1$，从而使最小生成树（MST）唯一。

最后一个示例对应的图片：

例如，你可以将边 $(1, 5)$ 和 $(2, 4)$ 的权值各增加 $1$，从而使最小生成树（MST）唯一。