蛮不错的一道题，遗憾就遗憾在数据范围会导致暴力轻松跑过。
最小生成树的两个性质：
不同的最小生成树，相同权值使用的边数一定相同。
不同的最小生成树，将其都去掉同一个权值的所有边，其连通性一致。
这样我们随便跑一个\(MST\)，就可以知道所有\(MST\)边的构造情况。由于性质二，我们可以考虑枚举每一种权值的所有边，保留所有非此权值的树边，看可以连出来多少种不同的最小生成树。也就是按照权值构造最小生成树，这个过程满足乘法原理。
#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 100 + 5;
const int M = 1000 + 5;
const int Mod = 31011;struct Len {int u, v, w;bool operator < (Len rhs) const {return w < rhs.w;}
}l[M];vector <Len> v;int n, m, S[N];int find (int x) {return S[x] == x ? x : S[x] = find (S[x]);
}vector <int> val, use, tot;vector <int> :: iterator it;void kruskal () {sort (l + 1, l + 1 + m);for (int i = 0; i <= n; ++i) S[i] = i;for (int i = 1; i <= m; ++i) {int fu = find (l[i].u);int fv = find (l[i].v);it = lower_bound (val.begin (), val.end (), l[i].w); if (it == val.end ()) {val.push_back (l[i].w);use.push_back (0);tot.push_back (1);} else {tot[it - val.begin ()]++;}if (fu != fv) {S[fu] = fv;it = lower_bound (val.begin (), val.end (), l[i].w); use[it - val.begin ()]++;v.push_back (l[i]);}}
}int mat[N][N];int gauss (int n) {int ret = 1;for (int i = 1; i <= n; ++i) {for (int k = i + 1; k <= n; ++k) {while (mat[k][i]) {int d = mat[i][i] / mat[k][i];for (int j = i; j <= n; ++j) {(((mat[i][j] -= d * mat[k][j]) %= Mod) += Mod) %= Mod;}swap (mat[i], mat[k]); ret = -ret;}}(((ret *= mat[i][i]) %= Mod) += Mod) %= Mod;}return abs (ret);
}void add_edge (int u, int v) {mat[u][u]++; mat[v][v]++;mat[u][v]--;mat[v][u]--;
}int sep[N]; int solve () {kruskal ();if (v.size () < n - 1) return 0;int ans = 1;for (int i = 0; i < val.size (); ++i) {memset (mat, 0, sizeof (mat));if (use[i] == 0 || tot[i] == use[i]) continue;for (int j = 0; j <= n; ++j) S[j] = j;for (int j = 0; j < v.size (); ++j) {if (v[j].w != val[i]) {S[find (v[j].u)] = find (v[j].v);}}int cnt = 0;for (int i = 1; i <= n; ++i) {sep[++cnt] = find (i);}sort (sep + 1, sep + 1 + cnt);cnt = unique (sep + 1, sep + 1 + cnt) - sep - 1;for (int j = 1; j <= m; ++j) {if (l[j].w == val[i]) {int fu = find (l[j].u);int fv = find (l[j].v);fu = lower_bound (sep + 1, sep + 1 + cnt, fu) - sep;fv = lower_bound (sep + 1, sep + 1 + cnt, fv) - sep;add_edge (fu, fv);}}(ans *= gauss (use[i])) %= Mod;}return ans;
}signed main () {
// freopen ("data.in", "r", stdin);cin >> n >> m;for (int i = 1; i <= m; ++i) {static int u, v, w;cin >> u >> v >> w;l[i] = (Len) {u, v, w};}cout << solve () << endl;
}
