#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){
    x=0;int f=0;char s=getchar();
    while(!isdigit(s))f|=s=='-',s=getchar();
    while(isdigit(s))x=x*10+s-48,s=getchar();
    x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
    if(x<0)putchar('-'),x=-x;
    do{buf[++cc]=int(x%10);x/=10;}while(x);
    while(cc)putchar(buf[cc--]+'0');
}
const int N=4e5+10;
const ll mod=998244353;
int n,m;
struct edge{
    int x,y;ll w;
}e[N],e2[N];int sum[N],cnt;bool v[N];
vector<pair<int,int> >to[N];//first:vertex ; second:id
int fa[N],s[N];
bool cmp(edge p1,edge p2){
    return p1.w>p2.w;
}
int findfa(int x){
    return x==fa[x]?x:fa[x]=findfa(fa[x]);
}
int tp1,sta1[N];
int tp2,sta2[N];
bool check(){
    rep(i,1,tp1){
        if(sum[sta1[i]]==2||v[sta1[i]])return 0;
    }
    return 1;
}
void solve(){
    qr(n),qr(m);
    rep(i,1,m){
        int x,y,z;qr(x),qr(y),qr(z);
        if(x>y)swap(x,y);
        e[i]=(edge){x,y,z};
    }
    rep(i,1,m){
        int x=e[i].x,y=e[i].y;
        to[x].push_back({y,i});
        to[y].push_back({x+n,i});
    }
    rep(i,1,n){
        sort(to[i].begin(),to[i].end());
    }
    priority_queue<pair<ll,int> >q;
    rep(i,1,m){
        if(e[i].y==e[i].x+1||(e[i].x==1&&e[i].y==n)){
            sum[i]=1;
            q.push({-e[i].w,i});
        }
    }
    while(q.size()){
        int id=q.top().second;q.pop();
        if(sum[id]!=1||v[id])continue;
        v[id]=1;
        int st1=e[id].x,st2=e[id].y;
        tp1=tp2=0;
        ll val=e[id].w;
        int x=st2,y;
        bool bk1=1,bk2=1;
        for(;x!=st1;x=y){
            int l=0,r=(int)to[x].size()-1,mid,pos=-1;
            int lim;
            if(x<st1)lim=st1;
            else{
                lim=st1+n;if(x==st2)lim--;
            }
            while(l<=r){
                mid=(l+r)/2;
                if(to[x][mid].first<=lim)pos=mid,l=mid+1;
                else r=mid-1;
            }
            if(pos==-1){
                bk1=0;break;
            }
            int idd=to[x][pos].second;
            y=to[x][pos].first;if(y>n)y-=n;
            sta1[++tp1]=idd;
        }
        x=st1;
        for(;x!=st2;x=y){
            int l=0,r=(int)to[x].size()-1,mid,pos=-1;
            int lim;
            if(x==st1)lim=st2-1;
            else lim=st2;
            while(l<=r){
                mid=(l+r)/2;
                if(to[x][mid].first<=lim)pos=mid,l=mid+1;
                else r=mid-1;
            }
            if(pos==-1){
                bk2=0;break;
            }
            int idd=to[x][pos].second;
            y=to[x][pos].first;if(y>n)y-=n;
            sta2[++tp2]=idd;
        }
        if(bk1&&check()){
            rep(i,1,tp1){
                int idd=sta1[i];
                e[idd].w+=val;
                sum[idd]++;
                if(sum[idd]==1)q.push({-e[idd].w,idd});
            }
        }
        else{
            rep(i,1,tp2){
                int idd=sta2[i];
                e[idd].w+=val;
                sum[idd]++;
                if(sum[idd]==1)q.push({-e[idd].w,idd});
            }
        } 
    }
    rep(i,1,m)if(sum[i]==2){
        e2[++cnt]=e[i];
    }
    sort(e2+1,e2+cnt+1,cmp);
    rep(i,1,n){
        fa[i]=i;
        s[i]=1;
    }
    // cout<<"edge: "<<cnt<<endl;
    ll ans=0;
    rep(i,1,cnt){
        int x=e2[i].x,y=e2[i].y;
        x=findfa(x);
        y=findfa(y);
        ans+=e2[i].w%mod*s[x]%mod*s[y]%mod;
        ans%=mod;
        fa[x]=y;
        s[y]+=s[x];
    }
    qw(ans);puts("");
}
int main(){
    int tt;tt=1;
    while(tt--)solve();
    return 0;
}