记录编号	608227	评测结果	AAATTTTTTT
题目名称	3920.编辑题目	最终得分	30
用户昵称	会挽弯弓满月	是否通过	未通过
代码语言	C++	运行时间	21.009 s
提交时间	2025-10-24 17:16:09	内存使用	30.21 MiB

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=1e6+10,mod=998244353;
ll n,m;
struct node{
	ll to,val,nxt;
	bool flag;
}e[N<<1];
ll h[N],tot;
void add(ll u,ll v,ll w){
	e[++tot]={v,w,h[u]};
	h[u]=tot;
	return;
}
ll now;
queue<ll> q;
bool vis[N];
ll bfs(ll u){
	while(q.size()) q.pop();
	for(int i=1;i<=n;i++) vis[i]=0;
	vis[u]=1;q.push(u);
	ll v,w;
	while(q.size()){
		u=q.front();q.pop();
		for(ll i=h[u];i;i=e[i].nxt){
			if(e[i].flag) continue;
			v=e[i].to;w=e[i].val;
			if(w==now) return 1;
			if(!vis[v]){
				vis[v]=1;
				q.push(v);
			}
		}
	}
	return 0;
}
ll res,sum;
ll ksm(ll x,ll y){
	ll res=1;x%=mod;
	while(y){
		if(y&1) res=(res*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return res;
}
int main(){
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	ll u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	for(int i=1;i<=tot;i+=2){
		e[i].flag=1;
		e[i+1].flag=1;
		now=e[i].val;
		for(int s=1;s<=n;s++){
			res+=bfs(s);
		}
		e[i].flag=0;
		e[i+1].flag=0;
	}
	sum=n*m;
	ll t=ksm(sum,mod-2),ans;
	ans=res%mod*t%mod;
	printf("%lld",ans);
	return 0;
}