最小生成树求调

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define lop(i, x, y) for (int i = x; i >= y; i--)
#define sort stable_sort
using namespace std;
typedef long double ld;
const int MOD = 31011;
const int NR = 105;
int n, m;
struct Edge{
    int u, v, w;
    bool operator<(Edge y) const{
        return w < y.w;
    }
}p[1005];
int fa[NR];
int fd(int k){
    if (k == fa[k]) return k;
    return fa[k] = fd(fa[k]);
}
int a[NR][NR], du[NR];
int dj[NR], cur, rp[NR];
int ans = 1;
ld lap[NR][NR];
int seq[NR], tail = 0;
int gauss(){
    int ret = 1;
    rep(i, 1, tail - 1){
        int id = i;
        rep(j, i + 1, tail - 1){
            if (abs(lap[j][i]) > abs(lap[id][i])){
                id = j;
            }
        }
        if (id != i){
            swap(lap[id], lap[i]);
            ret *= -1;
        }
        rep(j, i + 1, tail - 1){
            ld tmp = lap[j][i];
            rep(k, 1, tail - 1){
                lap[j][k] -= tmp / lap[i][i] * lap[i][k];
            }
        }
    }
    return ret;
}
void sol(int L, int R){
    //cout << '#' << L << ' ' << R << endl;
    rep(i, 1, n){
        du[i] = 0;
        rep(j, 1, n){
            a[i][j] = 0;
            lap[i][j] = 0;
        }
    }
    cur = 0;
    rep(i, 1, n){
        dj[++cur] = fd(i);
        rp[i] = fd(i);
    }
    sort(dj + 1, dj + cur + 1);
    cur = unique(dj + 1, dj + cur + 1) - dj - 1;
    rep(i, L, R){
        int u = p[i].u, v = p[i].v;
        if (fd(u) != fd(v)){
            fa[fd(u)] = fd(v);
        }
        u = rp[u], v = rp[v];
        a[u][v]++, a[v][u]++, du[u]++, du[v]++;
    }
    rep(dby, 1, n){
        tail = 0;
        rep(i, 1, cur){
            if (fd(dj[i]) == dby){
                seq[++tail] = dj[i];
            }
        }
        if (tail == 0 || tail == 1) continue;
        rep(i, 1, tail) rep(j, 1, tail){
            int aa = 0, dd = 0;
            if (i == j){
                aa = 0;
                dd = du[seq[i]];
            }else{
                aa = a[seq[i]][seq[j]];
                dd = 0;
            }
            lap[i][j] = 1.0 * dd - 1.0 * aa;
        }
        /*
        rep(i, 1, tail - 1){
            rep(j, 1, tail - 1)
                cout << lap[i][j] << ' ';
            cout << endl;
        }
        */
        ld rere = 1.0 * gauss();
        rep(i, 1, tail - 1){
            rere *= lap[i][i];
        }
        int re = ((int)((__int128)(round(rere)) % MOD) + MOD) % MOD;
        /*
        cout << "after: " << endl;
        rep(i, 1, tail - 1){
            rep(j, 1, tail - 1)
                cout << lap[i][j] << ' ';
            cout << endl;
        }
        //cout << ">>>" << re << endl;
        */
        ans = 1ll * ans * re % MOD;
    }
}
signed main(){
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n){
        fa[i] = i;
    }
    rep(i, 1, m){
        cin >> p[i].u >> p[i].v >> p[i].w;
    }
    sort(p + 1, p + m + 1);
    int L = 1;
    rep(i, 1, m){
        if (p[i].w != p[L].w){
            sol(L, i - 1);
            L = i;
        }
    }
    sol(L, m);
    rep(i, 1, n){
        if (fd(i) != fd(1)){
            cout << 0 << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}