伯兰有 $$$n$$$ 个城市和 $$$m$$$ 双向道路。第 $$$i$$$ 条道路连接城市 $$$x_i$$$ 和 $$$y_i$$$,并具有速度限制 $$$s_i$$$。道路网络允许每个人从任何城市到达任何其他城市。
贝尔兰交通部正在计划进行道路改革。
首先,维护所有 $$$m$$$ 道路的成本太高,因此 $$$m - (n - 1)$$$ 道路将被拆除,而剩余的 $$$(n - 1)$$$ 道路仍然允许从任何其他城市到达任何城市。形式上,其余道路应代表一棵无向树。
其次,其余道路的速度限制可能会改变。更改将按顺序进行,每次更改要么将某些道路上的速度限制提高 $$$1$$$,要么将其降低 $$$1$$$。由于改变速度限制需要大量工作,该部希望尽量减少改变的次数。
该部的目标是建立一个由 $$$(n - 1)$$$ 条道路组成的道路网,所有道路的最高速度限制恰好等于 $$$k$$$。他们分配给您的任务是计算必须执行的最小速度限制更改次数,以便道路网络满足他们的要求。
例如,假设 Berland 的初始地图如下所示,并且 $$$k = 7$$$:
那么最佳的行动方案之一是拆除道路 $$$1$$$–$$$4$$$ 和 $$$3$$$–$$$4$$$,然后将道路 $$$2$$$–$$$3$$$ 的速度限制降低 $$$1$$$,因此最终的道路网络如下所示:
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 部必须执行的最小更改次数,以便剩余 $$$(n - 1)$$$ 道路中的最大速度限制恰好为 $$$k$$$。
示例
输入 #1
4 4 5 7 4 1 3 1 2 5 2 3 8 2 4 1 3 4 4 4 6 5 1 2 1 1 3 1 1 4 2 2 4 1 4 3 1 3 2 1 3 2 10 1 2 8 1 3 10 5 5 15 1 2 17 3 1 15 2 3 10 1 4 14 2 5 8
输出 #1
1 3 0 0
注意
示例测试说明:
第一个测试用例在问题陈述中进行了描述。
在第二个测试用例中,道路网络最初看起来像这样:
该部可以拆除道路$$$1$$$–$$$2$$$、$$$3$$$–$$$2$$$和$$$3$$$–$$$4$$$,然后将道路$$$1$$$–$$$4$$$的速度限制提高三倍。
在第三个测试用例中,路网已经满足所有要求。
在第四个测试用例中,拆除道路 $$$1$$$–$$$2$$$ 就足够了,因此生成的道路网络满足要求。