该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

down

题目描述

这是一道经典题目。

给定一个 $n$ 个点 $m$ 条边的连通无向图，保证没有重边，自环，边有边权。

请求出这个图最小生成树的个数。

答案对 $10^9+7$ 取模。

请注意数据范围。

输入格式

本题包含多组数据。

第一行输入一个整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据。对于每组数据：

第一行输入两个整数 $n,m$ ，表示这个图的点数和边数。

接下来 $m$ 行，每行输入三个整数 $u,v,w$ ，表示一条边的两个端点和它的边权。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例 1

样例输入

2
3 3
1 2 1
1 3 2
2 3 3
3 3
1 2 1
1 3 1
2 3 1

样例输出

1
3

样例 2~5

见下发文件。

数据范围

对于每组数据，$1\le n\le 5*10^4,1\le m\le 10^5,1\le u<v\le n,1\le w\le 10^4$ 。

保证 $\sum n\le 5*10^4,\sum m \le 10^5$ 。

令 $D$ 为一组数据给出的图中最长的简单路径的长度。（定义长度为这条路径的点数）

保证对于每组数据， $D\le 7$ 。