题目描述

求最小生成树已经难不倒你了。

那么最小生成树的个数统计呢？

N 个点，编号为 1 ~ N。M条无向边。无自环，无重边。

问：该图有多少个不同的最小生成树？

注：两个最小生成树不同，当前仅当存在一条边不同时出现在这两个最小生成树中。

答案可能很大，你需要将其 mod 31011 后输出。

输入格式

第一行：两个整数 N, M

接下来 M 行：每行三个整数：u, v, w，表示点 u 和点 v 之间有一条权值为 w 的无向边。

注：本题数据保证具有相同权值的边不会超过 10 条。

输出格式

一个整数，表示答案 mod 31011

样例输入

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

样例输出

8

提示

100% 的数据：1 <= N <= 100; 1 <= M <= 1000; 1 <= u, v <= N; 1 <= w <= 10^9