Chenjb 在 2018 年 ICPC 亚洲区域赛徐州站遇到了一道棘手的题目，该题关于最小生成树（MST）。

最小生成树（Minimum Spanning Tree, MST）是指一个带权无向图中，连接所有顶点的边权之和最小的边集，且该边集构成一棵树。

在那道题目中，Chenjb 需要计算给定图中所有 MST 的总边权之和，这显然等于 MST 的总边权与不同 MST 总数的乘积。注意，当且仅当两棵生成树的边集不同时，它们被视为不同的生成树。

Chenjb 花了大约一个小时才利用 Kruskal 算法和矩阵树定理解决了那个问题。现在，Chenjb 相信你能比他更快地解决它。你将得到一个包含 $n$ 个顶点和 $m$ 条边的连通无向图 $G$，顶点编号为 $1, 2, \dots, n$。有趣的是，在 $G$ 中不存在经过 8 个顶点的简单路径。你需要计算给定图中所有 MST 的总边权之和。为了减小输出规模，你只需要输出答案对 $2^{30}$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 5\,000$)，表示测试数据的组数。

对于每组数据，第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 50\,000, 1 \le m \le 100\,000$)，分别表示图的顶点数和边数。

接下来的 $m$ 行，第 $i$ 行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le i \le m, 1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10\,000$)，表示连接顶点 $u_i$ 和 $v_i$ 的一条权值为 $w_i$ 的双向边。保证图中不存在重边，且保证图中不存在任何经过 8 个顶点的简单路径。

保证所有测试数据的 $n$ 之和不超过 $50\,000$，所有测试数据的 $m$ 之和不超过 $100\,000$。

输出格式

对于每组数据，输出一行，包含一个整数，表示答案对 $2^{30}$ 取模的结果。

样例

输入 1

2
3 3
1 2 4
1 3 5
2 3 6
3 3
1 2 4
1 3 4
2 3 4

输出 1

9
24