Road Reform

Description:

Input:

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$$$.

Output:

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$$$.

Sample Input:

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

Sample Output:

1
3
0
0

Note:

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.