容易发现即使两个最小生成树不同，它们两个各个权值的边的数量也相同，所以显然可以先跑一遍最小生成树统计是否有解后开始暴力搜索不同的最小生成树边，因为题目保证相同权值的边不超过10个，暴力搜索的实际复杂度足够，不用矩阵树，统计时用## Kruskal即可，其选边贪心刚好满足此解法所需，代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2010, MOD = 31011;
struct node {
	int u, v, w;
	bool operator < (const node& a) const {
		return w < a.w;
	}
}g[N];
map <int, int> ma;
int n, m, shu, fa[N], num[N];
inline int find(int x) {
	if(fa[x] == x) {
		return fa[x];
	} return fa[x] = find(fa[x]);
}
inline void dfs(int u, int ji, int w) {
	if(ji == num[ma[w]]) {
		shu = (shu + 1) % MOD;
		return;
	} if(g[u].w != w) return;
	int nfa[N];
	for(int i = 1;i <= n;i ++) {
		nfa[i] = fa[i];
	}
	int fx = find(g[u].u);
	int fy = find(g[u].v);
	if(fx != fy) {
		fa[fx] = fy;
		dfs(u + 1, ji + 1, w);
	}
	for(int i = 1;i <= n;i ++) {
		fa[i] = nfa[i];
	} dfs(u + 1, ji, w);
	return;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int cnt = 0; cin >> n >> m;
	for(int i = 1;i <= m;i ++) {
		cin >> g[i].u >> g[i].v >> g[i].w;
		if(!ma[g[i].w]) ma[g[i].w] = ++cnt;
	} sort(g + 1, g + 1 + m);
	for(int i = 1;i <= n;i ++) {
		fa[i] = i;
	} int sum = 0;
	for(int i = 1;i <= m;i ++) {
		int fx = find(g[i].u);
		int fy = find(g[i].v);
		if(fx != fy) {
			sum ++;
			num[ma[g[i].w]] ++;
			fa[fx] = fy;
		}
	}
	if(sum < n - 1) {cout << 0 << endl;  return 0;}
	for(int i = 1;i <= n;i ++) {
		fa[i] = i;
	} int ans = 1;
	for(int i = 1;i <= m;i ++) {
		if(ma[g[i].w]) {
			shu = 0; dfs(i, 0, g[i].w);
			ans *= shu; ans %= MOD;
			for(int j = i;j <= m;j ++) {
				if(g[i].w == g[j].w) {
					int fx = find(g[j].u);
					int fy = find(g[j].v);
					if(fx != fy) fa[fx] = fy;
				} else if(g[i].w == g[j - 1].w) break;
			} ma[g[i].w] = 0;
		} 
	} cout << ans % MOD << endl;
	return 0;
}