记录编号	583523	评测结果	EEEEEEEEEE
题目名称	编辑题目	最终得分	0
用户昵称	YunQian	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-10-18 10:39:24	内存使用	0.00 MiB

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf; 
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 
}
inline int read(){
	int x=0,f=1;char c=gc();
	for(;(c<'0'||c>'9');c=gc()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=gc())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}

void Assert(bool c,int L=0){if(!c){cout<<"Assertion Failed at "<<L<<endl;exit(0);}}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=3e6+5;

int n,m;

namespace Tarjan{
	int head[N],nxt[N],ver[N],tot=1;
	void adde(int u,int v){++tot,nxt[tot]=head[u],ver[tot]=v,head[u]=tot;}
	
	int dfn[N],low[N],dfc=0;
	bool bri[N];
	
	void tarjan(int u,int fr){
		dfn[u]=low[u]=++dfc;
		for(int i=head[u];i;i=nxt[i]){
			int v=ver[i];
			if((i^1)==fr)continue;
			if(dfn[v])cmin(low[u],dfn[v]);
			else{
				tarjan(v,i),cmin(low[u],low[v]);
				if(low[v]>dfn[u])bri[i]=bri[i^1]=1;
			}
		}
	}
	
	int bcc[N];
	void dfs(int u){
		for(int i=head[u];i;i=nxt[i]){
			int v=ver[i];
			if(bcc[v]||bri[i])continue;
			bcc[v]=bcc[u],dfs(v);
		}
	}
	
	int C=0;
	void label(){
		for(int i=1;i<=n;i++)if(!bcc[i])bcc[i]=++C,dfs(i);
	}
}

using Tarjan::bcc;
using Tarjan::adde;
using Tarjan::C;

vector<pair<int,pair<int,int> > >edges;
vector<int>E[N];

int cnt[N],fval[N],all[N];

#define fi first
#define se second
#define mk make_pair

vector<int>lsh;
vector<pair<int,int> >G[N];

int ans=0,sz[N];

void dfs(int u,int fval,int fa){
	int tmp=0;
	if(u!=1){
		cnt[fval]++;
		tmp=cnt[fval];
	}
	for(int w:E[u])cnt[w]++;
	for(auto e:G[u]){
		int v=e.fi,w=e.se;
		if(v==fa)continue;
		dfs(v,w,u),sz[u]+=sz[v];
	}
	if(u!=1){
		int D=cnt[fval]-tmp;
		if(D!=0)add(ans,sz[u]);
		if(D!=all[fval]-1)add(ans,n-sz[u]);
	}
}

signed main(void){

	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);

	n=read(),m=read();edges.resize(m),lsh.resize(m);
	for(int i=0;i<m;i++){
		int u=read(),v=read(),w=read();
		adde(u,v),adde(v,u);
		edges[i]=mk(w,mk(u,v)),lsh[i]=w;
	}
	
	sort(lsh.begin(),lsh.end());lsh.resize(unique(lsh.begin(),lsh.end())-lsh.begin());
	for(auto &e:edges)e.fi=lower_bound(lsh.begin(),lsh.end(),e.fi)-lsh.begin()+1;
	
	Tarjan::tarjan(1,0),Tarjan::label();
	
	ans=0;
	for(int i=1;i<=n;i++)sz[bcc[i]]++;
	for(auto e:edges){
		int u=e.se.fi,v=e.se.se;all[e.fi]++;
		u=bcc[u],v=bcc[v];if(u==v){E[u].emplace_back(e.fi);continue;}
		G[u].emplace_back(mk(v,e.fi)),G[v].emplace_back(mk(u,e.fi));
	}
	
	for(auto e:edges){
		int u=e.se.fi,v=e.se.se;
		if(bcc[u]!=bcc[v])continue;
		if(all[e.fi]>1)add(ans,n);
	}
	
	dfs(1,0,0);
	
	cout<<1ll*ans*inv(n)%mod*inv(m)%mod<<endl;

	return 0;
}