记录编号	583631	评测结果	AAAAAAAAAA
题目名称	编辑题目	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	3.230 s
提交时间	2023-10-19 20:23:49	内存使用	121.13 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int N=1000000+5;
const ll mod=998244353;
ll fst(ll x,ll y){ll ans=1;while(y){if (y&1)ans=ans*x%mod;x=x*x%mod,y>>=1;}return ans;}
int n,m,V;
vector<int>g[N],id[N],tr[N];
int w[N],tmp[N];
pii E[N];
int dfn[N],tim=0,low[N];
int st[N],top=0;
int cnt=0,vid[N],S[N];
bool brg[N];
void tarjan(int pt,int lst){
	dfn[pt]=low[pt]=++tim;
	st[++top]=pt;
	for (auto v:g[pt]){
		if (v==lst)continue;
		if (!dfn[v]){
			tarjan(v,pt);
			low[pt]=min(low[pt],low[v]);
		}else low[pt]=min(low[pt],dfn[v]);
	}
	if (low[pt]==dfn[pt]){
		int z;cnt++;
		do{
			z=st[top--];vid[z]=cnt;S[cnt]++;
		}while(z!=pt);
	}return ;
}
void build(){
	tarjan(1,0);
	for (int i=1;i<=m;i++){
		int u=vid[E[i].fi],v=vid[E[i].se];
		if (u!=v)tr[u].pb(v),tr[v].pb(u),brg[i]=1;
	}
	return ;
}
struct BIT{
	int c[N];
	void add(int x,int w){
		for (int i=x;i<=cnt;i+=i&(-i))c[i]+=w;
		return ;
	}
	int getsum(int x){
		int t=0;for (int i=x;i>0;i-=i&(-i))t+=c[i];
		return t;
	}
	int query(int x,int y){
		return getsum(y)-getsum(x-1);
	}
}T;
int sz[N],dep[N];ll ans=0;
void dfs(int pt,int fa){
	dfn[pt]=++tim;sz[pt]=1;
	dep[pt]=dep[fa]+1;
	for (auto v:tr[pt]){
		if (v==fa)continue;
		dfs(v,pt);sz[pt]+=sz[v];
		S[pt]+=S[v];
	}return ;
}
void solve(){
	memset(dfn,0,sizeof(dfn)),tim=0;
	dfs(1,0);
	for (int i=1;i<=m;i++){
		if (!brg[i]&&id[w[i]].size()>1)ans+=n;
		if (brg[i]&&dep[vid[E[i].fi]]<dep[vid[E[i].se]])swap(E[i].fi,E[i].se);
	}
	for (int i=1;i<=V;i++){
		for (auto j:id[i])T.add(dfn[vid[E[j].fi]],1);
		for (auto j:id[i]){
			if (!brg[j])continue;
			int u=vid[E[j].fi];
			int cur=T.query(dfn[u],dfn[u]+sz[u]-1),p=0;
			if (cur>1)ans+=S[u],p+=S[u];
			if (id[i].size()-cur>0)ans+=n-S[u],p+=n-S[u];
		}
		for (auto j:id[i])T.add(dfn[vid[E[j].fi]],-1);
	}return ;
}
inline int read(){
	int ans=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int main(){
	freopen ("edit.in","r",stdin);
	freopen ("edit.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		E[i].fi=read(),E[i].se=read(),w[i]=read();
		g[E[i].fi].pb(E[i].se),g[E[i].se].pb(E[i].fi);
		tmp[i]=w[i];
	} 
	sort(tmp+1,tmp+m+1);V=unique(tmp+1,tmp+m+1)-tmp-1;
	for (int i=1;i<=m;i++){
		w[i]=lower_bound(tmp+1,tmp+V+1,w[i])-tmp;
		id[w[i]].pb(i);
	}
	build();
	solve();
	printf("%lld\n",ans%mod*fst(1ll*n*m%mod,mod-2)%mod);
	return 0;
}