#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 1e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
#define LC tree[x].lc
#define RC tree[x].rc
#define mod 998244353
vector<pair<pair<ll,ll>,ll> > ins1[20020],del1[20020],ins2[20020],del2[20020];
pair<ll,pair<ll,ll> > e[20020];
ll n,m,rt1[20020],rt2[20020],tot=0,cnt=0,fa[20020],siz[20020],ans=0;
struct nd{
	ll t,pos,val;
};
il bl operator<(const nd &x,const nd &y){
	return x.val<y.val;
}
il nd operator+(const nd &x,const nd &y){
	return (nd){y.t,x.pos,x.val+y.val};
}
struct node{
	nd minn,hminn,lz,lzmin;
	ll lc,rc;
	il void addtag(nd tg,nd tgmin){
		hminn=min(hminn,minn+tgmin);
		lzmin=min(lzmin,lz+tgmin);
		minn=minn+tg;
		lz=lz+tg;
	}
}tree[10000010];
il void pushup(ll x){
	tree[x].minn=min(tree[LC].minn,tree[RC].minn);
	tree[x].hminn=min(tree[LC].hminn,tree[RC].hminn);
}
il void pushdown(ll x){
	if(tree[x].lz.t){
		tree[LC].addtag(tree[x].lz,tree[x].lzmin);
		tree[RC].addtag(tree[x].lz,tree[x].lzmin);
	}
	tree[x].lz=tree[x].lzmin=(nd){0,0,0};
}
void build(ll &x,ll l,ll r){
	x=++tot;
	tree[x]=(node){(nd){0,l,(ll)inf},(nd){0,l,(ll)inf},(nd){0,0,0},(nd){0,0,0},0,0};
	if(l==r) return;
	ll mid=(l+r)>>1;
	build(LC,l,mid);
	build(RC,mid+1,r);
}
void mdf(ll x,ll l,ll r,ll ql,ll qr,nd v){
	if(ql<=l&&r<=qr){
		tree[x].addtag(v,v);
		return;
	}
	tree[++tot]=tree[LC];
	tree[++tot]=tree[RC];
	LC=tot-1;
	RC=tot;
	pushdown(x);
	ll mid=(l+r)>>1;
	if(ql<=mid) mdf(LC,l,mid,ql,qr,v);
	if(mid<qr) mdf(RC,mid+1,r,ql,qr,v);
	pushup(x);
}
nd query(ll x,ll l,ll r,ll ql,ll qr,nd tg,nd tgmin){
	if(ql<=l&&r<=qr) return min(tree[x].hminn,tree[x].minn+tgmin);
	if(!tg.t){
		tg=tree[x].lz;
		tgmin=tree[x].lzmin;
	}
	else{
		tgmin=min(tree[x].lzmin,tree[x].lz+tgmin);
		tg=tree[x].lz+tg;
	}
	ll mid=(l+r)>>1;
	nd res=(nd){0,0,(ll)inf};
	if(ql<=mid) res=min(res,query(LC,l,mid,ql,qr,tg,tgmin));
	if(mid<qr) res=min(res,query(RC,mid+1,r,ql,qr,tg,tgmin));
	return res;
}
il void ins(ll l1,ll r1,ll l2,ll r2,ll w){
	if(l1>r1||l2>r2) return;
	ins1[l1].push_back(MP(MP(l2,r2),w));
	del1[r1+1].push_back(MP(MP(l2,r2),w));
	ins2[r2].push_back(MP(MP(l1,r1),w));
	del2[l2-1].push_back(MP(MP(l1,r1),w));
}
il nd calc(ll l,ll r){
	nd res1=(nd){0,0,(ll)inf},res2=(nd){0,0,(ll)inf};
	if(1<l) res1=query(rt1[l-1],1,n,l,r-1,(nd){0,0,0},(nd){0,0,0});
	res2=query(rt2[r],1,n,l,r-1,(nd){0,0,0},(nd){0,0,0});
	if(res1<res2) return res1;
	return (nd){res2.pos,res2.t,res2.val};
}
void solve(ll l,ll r){
	if(l==r) return;
	nd tmp=calc(l,r);
	e[++cnt]=MP(tmp.val,MP(l,r));
	if(tmp.t<l) swap(tmp.t,tmp.pos);
	solve(l,tmp.t);
	solve(tmp.t+1,r);
}
ll find(ll x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	n=read();
	m=read();
	fr(i,1,m){
		ll u=read(),v=read(),w=read();
		if(u>v) swap(u,v);
		ins(1,u-1,u,v-1,w);
		ins(u,v-1,v,n,w);
	}
	build(rt1[0],1,n);
	del1[1].push_back(MP(MP(1,n),(ll)inf));
	del2[n].push_back(MP(MP(1,n),(ll)inf));
	fr(i,1,n){
		rt1[i]=rt1[i-1];
		fr(j,0,(ll)ins1[i].size()-1){
			tree[++tot]=tree[rt1[i]];
			rt1[i]=tot;
			mdf(rt1[i],1,n,ins1[i][j].fir.fir,ins1[i][j].fir.sec,(nd){i,0,ins1[i][j].sec});
		}
		fr(j,0,(ll)del1[i].size()-1){
			tree[++tot]=tree[rt1[i]];
			rt1[i]=tot;
			mdf(rt1[i],1,n,del1[i][j].fir.fir,del1[i][j].fir.sec,(nd){i,0,-del1[i][j].sec});
		}
	}
	build(rt2[n+1],1,n);
	pfr(i,n,1){
		rt2[i]=rt2[i+1];
		fr(j,0,(ll)ins2[i].size()-1){
			tree[++tot]=tree[rt2[i]];
			rt2[i]=tot;
			mdf(rt2[i],1,n,ins2[i][j].fir.fir,ins2[i][j].fir.sec,(nd){i,0,ins2[i][j].sec});
		}
		fr(j,0,(ll)del2[i].size()-1){
			tree[++tot]=tree[rt2[i]];
			rt2[i]=tot;
			mdf(rt2[i],1,n,del2[i][j].fir.fir,del2[i][j].fir.sec,(nd){i,0,-del2[i][j].sec});
		}
	}
	solve(1,n);
	sort(e+1,e+cnt+1);
	fr(i,1,n) fa[i]=i;
	fr(i,1,n) siz[i]=1;
	pfr(i,cnt,1){
		ll x=find(e[i].sec.fir),y=find(e[i].sec.sec);
		ans+=siz[x]*siz[y]*e[i].fir;
		fa[y]=x;
		siz[x]+=siz[y];
	}
	write((ans%mod+(n*(n-1)/2)*2000000000%mod)%mod);
}