记录编号	608216	评测结果	AAAAAAAAAA
题目名称	3920.编辑题目	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	6.046 s
提交时间	2025-10-24 15:37:29	内存使用	102.09 MiB

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e6+10,M=2e6+10;
int n,m,ver[N],to[M],nxt[M],val[M],idx=1,mk[M],w[N];
int dfn[N],low[N],tot,dcc,id[M],from[N],ID,dn[N];
int vis[N],cnt,siz[N],fath[N];
map<int,int>H;
vector<int>G[N],Edge[N];
long long ksm(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void add(int x,int y,int z){
	to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,val[idx]=z;
}
void tarjan(int u,int edge){
	dfn[u]=low[u]=++tot;
	for(int i=ver[u];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])mk[i]=mk[i^1]=1;
		}else if((i^1)!=edge){
			low[u]=min(low[u],dfn[v]);
		}
	}
	return;
}
void dfs(int x){
	from[x]=dcc,w[dcc]++,vis[x]=1;
	for(int i=ver[x];i;i=nxt[i]){
		if(mk[i])continue;
		id[i]=id[i^1]=dcc;
		int y=to[i];
		if(!vis[y])dfs(y);
	}
	return;
}
void Add(int x,int y){
	G[x].push_back(y);
}
void DFS(int x,int fa){
	dn[x]=++cnt,siz[x]=1;
	fath[x]=fa;
	for(auto y:G[x]){
		if(y==fa)continue;
		DFS(y,x);
		siz[x]+=siz[y];
		w[x]+=w[y];
	}
	return;
}
int c[N];
void add(int x,int y){
	for(;x<=dcc;x+=(x&-x))c[x]+=y;
	return;
}
int qry(int x){
	int cnt=0;
	for(;x>0;x-=(x&-x))cnt+=c[x];
	return cnt;
}
int ask(int u){
	return qry(dn[u]+siz[u]-1)-qry(dn[u]-1);
}
signed main(){
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout); 
	scanf("%lld %lld",&n,&m);
	for(int i=1,u,v,val;i<=m;i++){
		scanf("%lld %lld %lld",&u,&v,&val);
		if(!H.count(val))H[val]=++ID;
		val=H[val],add(u,v,val),add(v,u,val);
		Edge[val].push_back(idx);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(1,0);
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dcc++;
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=ver[i];j;j=nxt[j]){
			if(from[i]!=from[to[j]]){
				Add(from[i],from[to[j]]);
			}
		}
	}
	long long ans=n*m;
	DFS(1,0);
	for(int i=1;i<=ID;i++){
		if(Edge[i].size()==1){
			ans-=n;
		}else{
			int u,v;
			for(auto pat:Edge[i]){
				u=to[pat],v=to[pat^1];
				if(!mk[pat])add(dn[id[pat]],1);
				else{
					u=from[u],v=from[v];
					if(u==fath[v])swap(u,v);
					add(dn[u],1);
				}
			}
			for(auto pat:Edge[i]){
				if(mk[pat]){
					u=from[to[pat]],v=from[to[pat^1]];
					if(u==fath[v])swap(u,v);
					if(ask(u)==1)ans-=w[u];
					if(ask(u)==Edge[i].size())ans-=n-w[u];
				}
			}
			for(auto pat:Edge[i]){
				u=to[pat],v=to[pat^1];
				if(!mk[pat])add(dn[id[pat]],-1);
				else{
					u=from[u],v=from[v];
					if(u==fath[v])swap(u,v);
					add(dn[u],-1);
				}
			}
		}
	}
	ans%=mod;
	ans=ans*ksm(1ll*n*m%mod,mod-2)%mod;
	printf("%lld\n",ans);
	return 0;
}