9718: Changing Minimum Spanning Tree

An undirected graph is a graph where any edge can be traversed in both directions. A simple graph is a graph that does not have duplicate edges or self-loops. A connected graph is a graph in which there exists at least one path between any two vertices.

A spanning tree of an undirected graph is a connected subgraph that includes all the vertices of the graph and some of its edges, where there exists exactly one path between any two vertices. An undirected graph can have edge weights, and the spanning tree with the minimum sum of edge weights is called the minimum spanning tree.

Given a weighted undirected simple graph with $n$ vertices and $m$ edges, where the weight of each edge is required to be an integer between $1$ and $k$, now we want to add one more edge under the weight constraint, such that the new graph is a simple graph that has at least one spanning tree, and the newly added edge must be included in any minimum spanning tree of it. Please help calculate how many ways to do that, and output the number of ways in modulo (10⁹+7).

The first line contains an integer $T$ (1<=T<=10⁵), indicating the number of test cases.
Then follow $T$ test cases. For each test case:
The first line contains three integers $n$, $m$ and $k$ .
The next $m$ lines describe the given simple graph. Each line of them contains three integers $u$, $v$, and $w$ (1≤u,v≤n1 \leq u, v \leq n1≤u,v≤n, $u\ne v$, 1≤w≤k1 \leq w \leq k1≤w≤k), representing an edge of weight $w$ connecting $u$ and $v$.
It is guaranteed that the sum of $N$ and the sum of $M$ over $T$ test cases do not exceed 5*10⁵ and 10⁶, respectively.

For each test case, output an integer in one line, representing the number of ways, in modulo (10⁹+7), to add an edge meeting the requirements.