You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

某国有 $n$ 个城市（编号从 $1$ 到 $n$）和 $m$ 条双向道路。

第 $i$ 条道路连接城市 $x_i$ 和 $y_i$，限速为 $s_i$。

这些道路保证每个人都可以往来任意两个城市之间。

现在州长小 Z 正计划对道路进行改革。

首先，维护所有 $m$ 条道路的成本太高，因此将放弃 $m-(n-1)$ 条道路，但同时要保证剩余的 $n-1$ 条道路仍能连通任意两个城市。

其次，剩余道路的限速可能会发生变化。更改将按顺序进行，每次更改要么将某条道路的限速提高 $1$，要么降低 $1$。由于更改速度限制需要大量工作，州长小 Z 希望尽量减少更改次数。

经过速度调整后，小 Z 的目标是剩下的 $n-1$ 条道路不仅连通任意两个城市，并且这 $n-1$ 条道路的速度限制中的最大值恰好等于 $k$。他给你分配了一项任务，请你来帮他计算他们必须执行的速度限制更改次数的最小值，使得结果满足他们的要求。你可以自由选择要放弃哪 $m-(n-1)$ 条道路。

输入格式

从 speed.in 文件读入数据。

第一行包含三个整数 $n,m,k$， 分别表示城市数量、道路数量和所需的最高限速。

接下来是 $m$ 行。第 $i$ 行包含三个整数 $x_i,y_i$ 和 $s_i$，分别表示第 $i$ 条道路连接的城市和该道路的限速。所有道路都是双向的。

保证道路网络是连通的（即沿着道路行驶可以从任意一个城市到达任意一个城市）。

输出格式

输出到 speed.out 文件。

输出一行一个整数，表示必须执行的最少更改次数，以便剩余 $n-1$ 条道路中的最大速度限制恰好为 $k$ 。

样例

4 5 7
4 1 10
1 2 8
2 3 8
2 4 1
3 4 9

2

最优方案之一是放弃连接$1$和$4$的道路，以及连接$3$和$4$的道路，然后将连接$1$和$2$的道路限速降低$1$，再将连接$2$和$3$的道路限速降低$1$。

样例 2

点击链接 ex_speed2.in 和 ex_speed2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于全部数据：

$2\le n\le 2\times 10^5, n-1\le m\le \min(2\times 10^5, \frac{n(n-1)}{2}), 1\le k\le 10^9$

$1\le x_i,y_i\le n,x_i\neq y_i,1\le s_i\le 10^9$

子任务 1（20 分）：保证所有道路的 $s_i\le k$。

子任务 2（20 分）：保证所有道路的 $s_i\ge k$。

子任务 3（20 分）：保证 $n \le 10^3$。

子任务 4（40 分）：没有其他限制。