CF1468J.Road Reform

There are $n$ cities and $m$ bidirectional roads in Berland. The $i$-th road connects the cities $x_i$ and $y_i$, and has the speed limit $s_i$. The road network allows everyone to get from any city to any other city.

The Berland Transport Ministry is planning a road reform.

First of all, maintaining all $m$ roads is too costly, so $m - (n - 1)$ roads will be demolished in such a way that the remaining $(n - 1)$ roads still allow to get to any city from any other city. Formally, the remaining roads should represent an undirected tree.

Secondly, the speed limits on the remaining roads might be changed. The changes will be done sequentially, each change is either increasing the speed limit on some road by $1$, or decreasing it by $1$. Since changing the speed limit requires a lot of work, the Ministry wants to minimize the number of changes.

The goal of the Ministry is to have a road network of $(n - 1)$ roads with the maximum speed limit over all roads equal to exactly $k$. They assigned you the task of calculating the minimum number of speed limit changes they have to perform so the road network meets their requirements.

For example, suppose the initial map of Berland looks like that, and $k = 7$:

Then one of the optimal courses of action is to demolish the roads $1$–$4$ and $3$–$4$, and then decrease the speed limit on the road $2$–$3$ by $1$, so the resulting road network looks like that:

伯兰德有 $n$ 座城市和 $m$ 条双向道路。第 $i$ 条道路连接城市 $x_i$ 和 $y_i$，且限速为 $s_i$。该道路网络保证任意两座城市之间均可互相到达。

伯兰德交通部正计划开展一项道路改革。

首先，维护全部 $m$ 条道路成本过高，因此将拆除其中 $m - (n - 1)$ 条道路，使得剩余的 $(n - 1)$ 条道路仍能保证任意两座城市之间均可互相到达。形式上，剩余道路应构成一棵无向树。

其次，剩余道路上的限速可能被调整。调整将按顺序进行，每次操作要么将某条道路的限速增加 $1$，要么减少 $1$。由于调整限速工作量巨大，交通部希望最小化调整次数。

交通部的目标是：最终保留的 $(n - 1)$ 条道路所构成的路网中，所有道路的最高限速恰好等于 $k$。他们委派你计算为达成此目标所需的最小限速调整次数。

例如，假设伯兰德初始地图如下所示，且 $k = 7$：

则一种最优方案是：拆除道路 $1$–$4$ 和 $3$–$4$，然后将道路 $2$–$3$ 的限速降低 $1$，最终路网如下所示：

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $n - 1 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2})$; $1 \le k \le 10^9$) — the number of cities, the number of roads and the required maximum speed limit, respectively.

Then $m$ lines follow. The $i$-th line contains three integers $x_i$, $y_i$ and $s_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$; $1 \le s_i \le 10^9$) — the cities connected by the $i$-th road and the speed limit on it, respectively. All roads are bidirectional.

The road network in each test case is connected (that is, it is possible to reach any city from any other city by traveling along the road), and each pair of cities is connected by at most one road.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. Similarly, the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 2 \cdot 10^5$；$n - 1 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2})$；$1 \le k \le 10^9$）—— 分别表示城市的数量、道路的数量以及要求的最大限速。

接下来是 $m$ 行。第 $i$ 行包含三个整数 $x_i$、$y_i$ 和 $s_i$（$1 \le x_i, y_i \le n$；$x_i \ne y_i$；$1 \le s_i \le 10^9$）—— 分别表示第 $i$ 条道路所连接的两个城市及其限速。所有道路均为双向道路。

每个测试用例中的道路网络是连通的（即任意两个城市之间均存在一条沿道路的路径），且每对城市之间至多由一条道路连接。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。类似地，所有测试用例的 $m$ 之和也不超过 $2 \cdot 10^5$。

For each test case, print one integer — the minimum number of changes the Ministry has to perform so that the maximum speed limit among the remaining $(n - 1)$ roads is exactly $k$.

对于每个测试用例，输出一个整数——即交通部需要执行的最少修改次数，使得剩余 $(n - 1)$ 条道路中的最大限速值恰好为 $k$。

The explanation for the example test:

The first test case is described in the problem statement.

In the second test case, the road network initially looks like that:

The Ministry can demolish the roads $1$–$2$, $3$–$2$ and $3$–$4$, and then increase the speed limit on the road $1$–$4$ three times.

In the third test case, the road network already meets all the requirements.

In the fourth test case, it is enough to demolish the road $1$–$2$ so the resulting road network meets the requirements.

示例测试的解释：

第一个测试用例已在题目描述中给出。

在第二个测试用例中，道路网络初始状态如下所示：

交通部可以拆除道路 $1$–$2$、$3$–$2$ 和 $3$–$4$，然后将道路 $1$–$4$ 的限速提升三次。

在第三个测试用例中，道路网络已满足全部要求。

在第四个测试用例中，仅需拆除道路 $1$–$2$，即可使最终的道路网络满足全部要求。