#include<bits/stdc++.h>
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define ll long long
using namespace std;
const int N=1e6+10,p=998244353;
int n,m,u[N],v[N];ll w[N];
struct edge{
	int u,v;ll w;
	bool operator<(const edge h)const{return w>h.w;}
}e[N];int tot;
vector<pair<int,int> > g[N];
set<pair<ll,int> > s;
int nxt[N];
int fa[N],sz[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
signed main(){
	file("flow");
	scanf("%d%d",&n,&m);
	for(int x,y,z,i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		int p=i<<1,q=p|1;
		u[p]=x,v[p]=y,w[p]=z,g[x].push_back(make_pair(y,p));
		v[q]=x,u[q]=y,w[q]=z,g[y].push_back(make_pair(x,q));
	}
	for(int i=1;i<=n;i++){
		sort(g[i].begin(),g[i].end());
		for(int j=0;j+1<g[i].size();j++)nxt[g[i][j+1].second^1]=g[i][j].second;
		nxt[g[i][0].second^1]=g[i][g[i].size()-1].second;
	}
    int r=g[1][g[1].size()-1].second,x=r;
    while(nxt[x]!=r)s.insert(make_pair(w[x],x)),x=nxt[x];
    s.insert(make_pair(w[x],x));
    for(int i=1;i<=m-n+1;i++){
    	int id=s.begin()->second;s.erase(s.begin());
    	int r,x;r=x=id^1;
    	ll val=w[x];
    	while(nxt[x]!=r){
			x=nxt[x];
    		w[x^1]+=val;
    		if(s.count(make_pair(w[x],x^1))){
    			s.erase(make_pair(w[x],x^1));
    			e[++tot]={u[x],v[x],w[x]+=val};
			}else s.insert(make_pair(w[x]+=val,x));
		}
	}
	sort(e+1,e+tot+1);
	for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;
	int ans=0;
	for(int i=1;i<=tot;i++){
		int u=find(e[i].u),v=find(e[i].v);
		if(u==v)continue;
		ans=(ans+e[i].w%p*sz[u]%p*sz[v]%p)%p;
		fa[u]=v,sz[v]+=sz[u];
	}
	printf("%d\n",ans);
}