题目描述

无向图是任意一条边可以双向移动的图，简单图是不存在重复边和自环的图，连通图是图中任意两点间存在至少一条路径的图。

一个无向图的生成树是包含该图所有顶点和部分边的连通子图，且任意两点间恰好有一条路径。无向图可以带有边权，此时边权之和最小的生成树称为最小生成树。

给定一张含有 $n$ 个点与 $m$ 条边的带权无向简单图，其中每条边权要求是 $1$ 到 $k$ 之间的整数，现在我们希望再加一条满足边权限制的边进去，使得新图是一张存在至少一个生成树的简单图，且新加的边一定在它的任何一个最小生成树里，请你帮忙计算有多少种方案，输出方案数模 $(10^9 + 7)$ 的值。

输入格式

第一行包含一个整数 $T (1 \leq T \leq 10^5)$，表示测试用例的数量。

接下来是 $T$ 个测试用例。对于每个测试用例：

第一行包含三个整数 $n$、$m$ 和 $k (1 \leq n \leq 10^5, 0 \leq m \leq \min \left(2 \times 10^5, \frac{n(n-1)}{2}\right), 1 \leq k \leq 10^9)$。

接下来的 $m$ 行描述给定的简单图，每行包含三个整数 $u$、$v$ 和 $w (1 \leq u, v \leq n, u \neq v, 1 \leq w \leq k)$，表示一条连接 $u$ 和 $v$ 的权重为 $w$ 的边。

保证 $T$ 个测试用例中 $N$ 之和、$M$ 之和分别不超过 $5 \times 10^5$ 和 $10^6$。

输出格式

对于每个测试用例，在一行中输出一个整数，表示满足要求的加边方案数模 $(10^9 + 7)$。

5
3 2 2
1 2 1
2 3 2
3 3 5
1 2 3
2 3 4
1 3 5
2 1 3
1 2 3
6 6 5
1 2 3
1 3 1
2 4 2
3 5 2
2 6 4
5 6 5
2 0 25

1
0
0
20
25