【题解】

大概就是先求出mct。

然后有个结论可以证明：就是在不同的mct中，每种权值的边用的是一样的。

然后我们就求出mct然后枚举就行啦

# include <stdio.h>
# include <algorithm>

using namespace std;

int n, m, fa[666666];
struct edge {
	int u, v, w;
}e[666666];
int ls[666666], lsn=0, MCT=0;
int used[666666];
inline int cmp(edge a, edge b) {
	return a.w < b.w;
}
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}

inline bool chk(int pos, int x) {
	for (int i=1; i<=n; ++i) fa[i] = i;
	int cnt=0, mct = e[pos].w * used[e[pos].w];
	for (int i=pos; e[pos].w == e[i].w; ++i) {
		if(x&1) {
			int fu = getf(e[i].u), fv = getf(e[i].v);
			if(fu != fv) {
				fa[fu] = fv;
				++cnt;
			}
		}
		x >>= 1;
	}
	if(cnt == n-1) return mct == MCT;
	bool ok=0;
	for (int i=1; i<=m; ++i) {
		if(e[i].w == e[pos].w) continue;
		int fu = getf(e[i].u), fv = getf(e[i].v);
		if(fu == fv) continue;
		fa[fu] = fv;
		mct += e[i].w;
		++cnt;
		if(cnt == n-1) {
			ok=1;
			break;
		}
	}
	return ok && mct == MCT;
}

int main() {

	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; ++i) {
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
		ls[++lsn] = e[i].w;
	}
	sort(ls+1, ls+lsn+1);
	lsn=unique(ls+1, ls+lsn+1) - ls;
	for (int i=1; i<=m; ++i) 
		e[i].w = lower_bound(ls+1, ls+lsn+1, e[i].w) - ls;
	
	sort(e+1, e+m+1, cmp);
	
	for (int i=1; i<=n; ++i) fa[i] = i;
	
	int cnt=0;
	bool ok=0;
	
	for (int i=1; i<=m; ++i) {
		int fu = getf(e[i].u), fv = getf(e[i].v);
		if(fu == fv) continue;
		fa[fu] = fv;
		used[e[i].w] ++;
		MCT += e[i].w;
		++cnt;
		//printf("cnt=%d, MCT=%d\n", cnt, MCT);
		if(cnt == n-1) {
			ok=1;
			break;
		}
	}
	//printf("%d\n", MCT);
	//printf("USED=%d\n", used[2]);
	if(! ok) {
		puts("0");
		//puts("gg");
		return 0;
	}
	
	int ans = 1, j, now;
	
	for (int i=1; i<=m; i=j) {
		j=i+1;
		while(e[i].w == e[j].w) ++j;
		if(used[e[i].w]) {
			now = 0;
			int gs = j-i;
//			printf("To: %d\n", (1<<gs));
			for (int k=0; k<(1<<gs); ++k) {
				int gs2 = 0, kk = k;
				while(kk) {
					gs2 += kk&1;
					kk >>= 1;
				}
//				printf("k=%d, gs=%d\n", k, gs2);
				if(gs2 != used[e[i].w]) continue;
				if(chk(i, k)) ++now;
			}
			ans = ans * now % 31011;
		}
	}	
	
	
	printf("%d\n", ans);
	return 0;
}