记录编号	583537	评测结果	AAAAAAEAAA
题目名称	编辑题目	最终得分	90
用户昵称	HzmQwQ	是否通过	未通过
代码语言	C++	运行时间	3.489 s
提交时间	2023-10-18 15:31:07	内存使用	121.13 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

#define MAXN 1000005
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))

using namespace std;

typedef long long ll;

struct edge {
    int u, v, w;
} Edge[MAXN];

struct node {
    int to, wgt;
};

const ll M = 998244353LL;
int n, m, wt[MAXN], dfn[MAXN], low[MAXN], dfncnt, scc[MAXN], vwt[MAXN], scccnt, son_sz[MAXN], dfnT[MAXN], dfnTcnt, mxdfT[MAXN];
bool instack[MAXN];
vector <node> G[MAXN];
vector <int> swe[MAXN], T[MAXN];
stack <int> st;
int tmpdfn[MAXN];

int qread() {
    int x = 0;
    char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') {
        x = 10 * x + c - '0';
        c = getchar();
    }
    return x;
}

ll quick_pow(ll base, ll xp) {
    ll ret = 1LL;
    while(xp > 0) {
        if(xp & 1LL) ret = (ret * base) % M;
        base = (base * base) % M;
        xp >>= 1LL;
    }
    return ret;
}

void tarjan(int u, int fr) {
    dfn[u] = low[u] = ++dfncnt;
    st.push(u);
    instack[u] = true;
    for(node nxt : G[u]) {
        int v = nxt.to;
        if(v == fr) continue;
        if(dfn[v] == 0) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else if(instack[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]) {
        ++scccnt;
        while(st.top() != u) {
            scc[st.top()] = scccnt;
            ++vwt[scccnt];
            instack[st.top()] = false;
            st.pop();
        }
        scc[st.top()] = scccnt;
        ++vwt[scccnt];
        instack[st.top()] = false;
        st.pop();
    }
    return ;
}

void getTr() {
    for(int i = 1; i <= m; i++) {
        if(scc[Edge[i].u] == scc[Edge[i].v]) continue;
        T[scc[Edge[i].u]].push_back(scc[Edge[i].v]);
        T[scc[Edge[i].v]].push_back(scc[Edge[i].u]);
    }
    return ;
}

void dfsTr(int u, int fr) {
    dfnT[u] = ++dfnTcnt;
    son_sz[dfnT[u]] = vwt[u];
    mxdfT[dfnT[u]] = dfnT[u];
    for(int v : T[u]) {
        if(v == fr) continue;
        dfsTr(v, u);
        son_sz[dfnT[u]] += son_sz[dfnT[v]];
        mxdfT[dfnT[u]] = max(mxdfT[dfnT[u]], mxdfT[dfnT[v]]);
    }
    return ;
}

int main() {
    freopen("edit.in", "r", stdin);
    freopen("edit.out", "w", stdout);
    n = qread(); m = qread();
    for(int i = 1; i <= m; i++) {
        Edge[i].u = qread(); Edge[i].v = qread(); Edge[i].w = qread();
        wt[i] = Edge[i].w;
    }
    sort(wt + 1, wt + m + 1);
    int ulen = unique(wt + 1, wt + m + 1) - wt - 1;
    for(int i = 1; i <= m; i++) {
        int pos = lower_bound(wt + 1, wt + ulen + 1, Edge[i].w) - wt;
        Edge[i].w = pos;
        swe[pos].push_back(i);
        G[Edge[i].u].push_back((node){Edge[i].v, Edge[i].w});
        G[Edge[i].v].push_back((node){Edge[i].u, Edge[i].w});
    }
    tarjan(1, 0);
    ll fr = quick_pow((ll)m, M - 2LL);
    ll frn = quick_pow((ll)n, M - 2LL);
    getTr();
    dfsTr(1, 0);
    ll ans = 0LL;
    for(int i = 1; i <= ulen; i++) {
        if(swe[i].size() == 1) continue;
        else {
            int slen = swe[i].size(), tlen = 0;
            for(int j = 0; j < swe[i].size(); j++) {
                int ed = swe[i][j];
                if(scc[Edge[ed].u] == scc[Edge[ed].v]) {
                    ans = (ans + (ll)n) % M;
                    tmpdfn[++tlen] = dfnT[scc[Edge[ed].u]];
                    continue;
                }
                tmpdfn[++tlen] = dfnT[scc[Edge[ed].u]];
                tmpdfn[++tlen] = dfnT[scc[Edge[ed].v]];
            }
            sort(tmpdfn + 1, tmpdfn + tlen + 1);
            for(int ed : swe[i]) {
                if(scc[Edge[ed].u] == scc[Edge[ed].v]) continue;
                int fad = min(dfnT[scc[Edge[ed].u]], dfnT[scc[Edge[ed].v]]), snd = max(dfnT[scc[Edge[ed].u]], dfnT[scc[Edge[ed].v]]);
                int mxs = mxdfT[snd];
                int pos1 = upper_bound(tmpdfn + 1, tmpdfn + tlen + 1, mxs) - tmpdfn;
                int pos2 = lower_bound(tmpdfn + 1, tmpdfn + tlen + 1, snd) - tmpdfn;
                int sz = pos1 - pos2 + 1;
                if(sz > 2) ans = (ans + (ll)son_sz[snd]);
                if(sz < tlen) ans = (ans + (ll)n - (ll)son_sz[snd]);
            }
            for(int j = 1; j <= tlen; j++) tmpdfn[j] = 0;
        }
    }
    printf("%lld\n", (((ans * fr) % M) * frn) % M);
    return 0;
}