记录编号	608205	评测结果	AAAAAATAAA
题目名称	3920.编辑题目	最终得分	90
用户昵称	wdsjl	是否通过	未通过
代码语言	C++	运行时间	5.557 s
提交时间	2025-10-24 14:36:09	内存使用	57.18 MiB

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 998244353;
const int N = 1e6 + 5;
const int L = 1e6 + 5;

struct E {
    int u, v, w;
} e[L];

struct A {
    int t, i, n;
} a[2 * L];

int h[N], c = 0;
int d[N], l[N], o[N], s[N], t;
bool ce[L];
int cc[L];
int n, m;

void ade(int u, int v, int id) {
    c++;
    a[c].t = v;
    a[c].i = id;
    a[c].n = h[u];
    h[u] = c;
}

void tj(int u, int pe) {
    d[u] = l[u] = ++t;
    s[u] = 1;
    for (int i = h[u]; i; i = a[i].n) {
        int v = a[i].t, id = a[i].i;
        if (id == pe) continue;
        if (!d[v]) {
            tj(v, id);
            s[u] += s[v];
            if (l[v] > d[u]) {
                ce[id] = 1;
                cc[id] = v;
            }
            l[u] = min(l[u], l[v]);
        } else {
            l[u] = min(l[u], d[v]);
        }
    }
    o[u] = t;
}

int inv(int x) {
    int r = 1, e = mod - 2;
    while (e > 0) {
        if (e % 2) r = r * x % mod;
        x = x * x % mod;
        e /= 2;
    }
    return r;
}

signed main() {
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        e[i] = {u, v, w};
        ade(u, v, i);
        ade(v, u, i);
    }
    t = 0;
    tj(1, -1);
    unordered_map<int, vector<int>> ew;
    for (int i = 0; i < m; i++) {
        ew[e[i].w].push_back(i);
    }
    int tot = 0;
    for (int i = 0; i < m; i++) {
        int w = e[i].w;
        auto& v = ew[w];
        int cw = v.size();
        if (!ce[i]) {
            if (cw > 1) {
                tot = (tot + n) % mod;
            }
        } else {
            if (cw == 1) continue;
            int vv = cc[i], sa = s[vv], sb = n - sa;
            int a = 0, b = 0;
            for (int id : v) {
                if (id == i) continue;
                E& ed = e[id];
                int u = ed.u, vvv = ed.v;
                bool inA_u = d[vv] <= d[u] && d[u] <= o[vv];
                bool inA_v = d[vv] <= d[vvv] && d[vvv] <= o[vv];
                if (inA_u && inA_v) a = 1;
                if (!inA_u && !inA_v) b = 1;
                if (a && b) break;
            }
            tot = (tot + 1LL * a * sa + 1LL * b * sb) % mod;
        }
    }
    int mu = (1LL * m * n) % mod;
    int id = inv(mu);
    int ans = (tot * id) % mod;
    cout << ans << endl;
    return 0;
}