#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
#define pb push_back
int n,m,s,l;
const int N=3e4,M=5e6,inf=2e9,mo=998244353;
struct xyz{int x,y,z;}b[N];
inline bool operator<(xyz a,xyz b){return a.z<b.z;};
struct Kazemaru{
	int rt[N],t;
	struct xds{int ls,rs,t,x;xyz c,d;}a[M];
	struct op{int l,r,c;};vector<op>q[N];
	#define mid (L+R)/2
	inline void New(int&id,int x){if(a[id].x<x)a[++t]=a[id],a[id=t].x=x;}
	inline void Add(int&id,int c,int x){New(id,x);a[id].t+=c;a[id].c.z+=c;a[id].c.x=x;a[id].d=min(a[id].c,a[id].d);}
	inline void xf(int id,int x){Add(a[id].ls,a[id].t,x);Add(a[id].rs,a[id].t,x);a[id].t=0;}
	inline void up(int id){a[id].c=min(a[a[id].ls].c,a[a[id].rs].c);a[id].d=min(a[a[id].ls].d,a[a[id].rs].d);}
	int bt(int L,int R){
		int id=++t;if(L<R)a[id]={bt(L,mid),bt(mid+1,R)};
		a[id].c=a[id].d={0,L,inf};return id;
	}
	void add(int&id,int L,int R,int l,int r,int c,int x){
		if(r<L||R<l)return;New(id,x);
		if(l<=L&&R<=r)return Add(id,c,x);xf(id,x);
		add(a[id].ls,L,mid,l,r,c,x);add(a[id].rs,mid+1,R,l,r,c,x);up(id);
	}
	xyz ask(int id,int L,int R,int l,int r){
		if(r<L||R<l||!id)return{0,0,inf};
		if(l<=L&&R<=r)return a[id].d;xf(id,n);
		return min(ask(a[id].ls,L,mid,l,r),ask(a[id].rs,mid+1,R,l,r));
	}
	#undef mid
	inline void ADD(int u,int v,int w){
		q[1].pb({u,v-1,w});q[u+1].pb({u,v-1,-w});
		q[u+1].pb({v,n,w});q[v+1].pb({v,n,-w});
	}
	inline void init(){
		rt[0]=bt(1,n);q[1].pb({1,n,-inf});
		f(i,1,n){
			rt[i]=rt[i-1];
			sort(q[i].begin(),q[i].end(),[&](op a,op b){return a.c>b.c;});
			for(op e:q[i])add(rt[i],1,n,e.l,e.r,e.c,i);
		}
	}
	inline xyz ASK(int u,int v){xyz a=ask(rt[u],1,n,u,v-1);return{min(a.x,u),a.y,a.z};}
}A,B;
int fa[N],sz[N],x,y,z;
int fifa(int x){return x==fa[x]?x:fa[x]=fifa(fa[x]);}
inline void add(int u,int v,int w){A.ADD(u,v,w);B.ADD(n-v+1,n-u+1,w);}
inline xyz ask(int u,int v){
	xyz a=A.ASK(u,v),b=B.ASK(n-v+1,n-u+1);
	return min(a,(xyz){n-b.y+1,n-b.x+1,b.z});
}
void clc(int l,int r){
	if(l==r)return;xyz e=ask(l,r);b[++m]={l,r,e.z};
	int p=e.x<=l?e.y:e.x-1;clc(l,p);clc(p+1,r);
}
signed main(){
	cin>>n>>m;
	f(i,1,m){
		cin>>x>>y>>z;
		x<y?add(x,y,z):add(y,x,z);
	}m=0;
	A.init();B.init();clc(1,n);
	sort(b+1,b+m+1);
	f(i,1,n)sz[fa[i]=i]=1;
	g(i,m,1){
		x=fifa(b[i].x);y=fifa(b[i].y);
		s=(s+sz[x]*sz[y]%mo*b[i].z)%mo;
		sz[x]+=sz[y];fa[y]=x;
	}
	cout<<(s+n*(n-1)/2*inf)%mo;
	return 0;
}