// #define _GLIBCXX_DEBUG
#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define fi first
#define se second
using namespace std; typedef long long ll;
constexpr int N=1e6+5,M=4e7+5; using pii = pair<int,int>;
#define k1 (k<<1)
#define k2 (k<<1|1)
// struct Tag{
//     vector<pii> o;
//     friend Tag operator* (const Tag& A,const Tag& B){
//         Tag res; res.o=A.o; res.o.insert(res.o.end(),B.o.begin(),B.o.end()); return res;
//     }
// };
// struct Data{
//     pair<int,pii> mn; pii cur;
//     Data() { mn.fi=1e9; mn.se=cur=pii(0,0); }
//     Data(const pair<int,pii>& A,const pii& B) { mn=A; cur=B; }
//     Data& operator*= (const Tag& tag){
//         for(auto [op,x]:tag.o){
//             if(op==0) cur.fi+=x;
//             else mn=min(mn,make_pair(cur.fi,pii(x,cur.se)));
//         }
//         return *this;
//     }
//     friend Data operator+ (const Data& A,const Data& B) { return Data(min(A.mn,B.mn),min(A.cur,B.cur)); }
// };
struct Tag{
    pii mn; int cur;
    Tag() { mn.fi=1e9; }
    Tag(const pii& A,const int& B) { mn=A; cur=B; }
    friend Tag operator* (const Tag& A,const Tag& B){
        Tag res;
        res.mn=min(A.mn,pii(A.cur+B.mn.fi,B.mn.se));
        res.cur=A.cur+B.cur;
        return res;
    }
    static Tag TagAdd(int x) { return Tag(pii(1e9,0),x); }
    static Tag TagRec(int t) { return Tag{pii(0,t),0}; }
};
struct Data{
    pair<int,pii> mn; pii cur;
    Data() { mn.fi=1e9; mn.se=cur=pii(0,0); }
    Data(const pair<int,pii>& A,const pii& B) { mn=A; cur=B; }
    Data& operator*= (const Tag& tag){
        mn=min(mn,make_pair(cur.fi+tag.mn.fi,pii(tag.mn.se,cur.se)));
        cur.fi+=tag.cur;
        return *this;
    }
    friend Data operator+ (const Data& A,const Data& B) { return Data(min(A.mn,B.mn),min(A.cur,B.cur)); }
};
class STree{
    int n,tot,lc[M],rc[M]; Data O[M]; Tag tag[M]; bool vis[M];
    int Copy(int k) { tot++; assert(tot<M); lc[tot]=lc[k]; rc[tot]=rc[k]; O[tot]=O[k]; tag[tot]=tag[k]; vis[tot]=vis[k]; return tot; }
    void setg(int k,Tag t) { O[k]*=t; tag[k]=tag[k]*t; vis[k]=1; }
    void pushdown(int k) { setg(lc[k],tag[k]); setg(rc[k],tag[k]); tag[k]=Tag{}; vis[k]=0; }
    void update(int k) { O[k]=O[lc[k]]+O[rc[k]]; }
    void build(int k,int l,int r){
        if(l==r) return O[k].cur.se=l,void();
        int mid=(l+r)>>1; build(lc[k]=++tot,l,mid); build(rc[k]=++tot,mid+1,r); update(k);
    }
    int add(int k,int l,int r,int ql,int qr,int x){
        int p=Copy(k); if(ql<=l&&r<=qr) return setg(p,Tag::TagAdd(x)),p;
        int mid=(l+r)>>1; assert(lc[k]&&rc[k]);
        if(vis[p]) { lc[p]=Copy(lc[k]); rc[p]=Copy(rc[k]); pushdown(p); }
        if(ql<=mid) lc[p]=add(lc[p],l,mid,ql,qr,x);
        if(mid+1<=qr) rc[p]=add(rc[p],mid+1,r,ql,qr,x);
        update(p); return p;
    }
    pair<int,pii> query(int k,int l,int r,int ql,int qr,Tag t){
        if(ql<=l&&r<=qr) { Data res=O[k]; res*=t; return res.mn; }
        int mid=(l+r)>>1; pair<int,pii> res(1e9,{0,0}); t=tag[k]*t;
        if(ql<=mid) res=min(res,query(lc[k],l,mid,ql,qr,t));
        if(mid+1<=qr) res=min(res,query(rc[k],mid+1,r,ql,qr,t));
        return res;
    }
public:
    void init(int _n) { n=_n; tot++; build(1,1,n); }
    int add(int k,int l,int r,int x) { return add(k,1,n,l,r,x); }
    int record(int k,int t) { int p=Copy(k); setg(p,Tag::TagRec(t)); return p; }
    pair<int,pii> query(int k,int l,int r) { auto res=query(k,1,n,l,r,Tag{}); assert(res.fi!=1e9); assert(res.fi>=0); return res; }
    int TOT() { return tot; }
}T;
int n,m,rt[20][N]; struct TREE { int x,y,z; } TR[N]; int Tcnt;
struct Rect { int x1,x2,y1,y2,z; }; vector<Rect> lis[N<<2];
void Add(int k,int l,int r,int x1,int x2,int y1,int y2,int z){
    lis[k].push_back(Rect{max(x1,l),min(x2,r),y1,y2,z}); if(x1<=l&&r<=x2) return;
    int mid=(l+r)>>1;
    if(x1<=mid) Add(k1,l,mid,x1,x2,y1,y2,z);
    if(mid+1<=x2) Add(k2,mid+1,r,x1,x2,y1,y2,z);
}
void Add(int x1,int x2,int y1,int y2,int z){
    // For(i,x1,x2) For(j,y1,y2) a[i][j]+=z;
    if(x1>x2||y1>y2) return;
    Add(1,1,n,x1,x2,y1,y2,z);
}
void build(int k,int l,int r,int d,int o){
    static vector<tuple<int,int,int>> oper[N];
    int mid=(l+r)>>1; For(i,l,r) oper[i].clear();
    for(auto [x1,x2,y1,y2,z]:lis[k]){
        if(x1<=mid&&mid+1<=x2){
            oper[mid].emplace_back(y1,y2,z);
            oper[x1-1].emplace_back(y1,y2,-z);
            oper[mid+1].emplace_back(y1,y2,z);
            oper[x2+1].emplace_back(y1,y2,-z);
        }
        else if(x2<=mid){
            oper[x2].emplace_back(y1,y2,z);
            oper[x1-1].emplace_back(y1,y2,-z);
        }
        else{ assert(mid+1<=x1);
            oper[x1].emplace_back(y1,y2,z);
            oper[x2+1].emplace_back(y1,y2,-z);
        }
    }
    int oo=o;
    Rev(i,mid,l){
        for(auto [y1,y2,z]:oper[i]) oo=T.add(oo,y1,y2,z);
        rt[d][i]=oo=T.record(oo,i);
    }
    oo=o;
    For(i,mid+1,r){
        for(auto [y1,y2,z]:oper[i]) oo=T.add(oo,y1,y2,z);
        rt[d][i]=oo=T.record(oo,i);
    }
    if(l==r) return;
    oo=o; for(auto [x1,x2,y1,y2,z]:lis[k]) if(x1==l&&x2==r) oo=T.add(oo,y1,y2,z);
    build(k1,l,mid,d+1,oo); build(k2,mid+1,r,d+1,oo);
}
pair<int,pii> query(int k,int l,int r,int d,int ql,int qr,int y1,int y2){
    if(l==r) return T.query(rt[d][l],y1,y2);
    int mid=(l+r)>>1;
    if(ql<=mid&&mid+1<=qr) return min(T.query(rt[d][ql],y1,y2),T.query(rt[d][qr],y1,y2));
    else if(qr<=mid) return query(k1,l,mid,d+1,ql,qr,y1,y2);
    else return assert(mid+1<=ql),query(k2,mid+1,r,d+1,ql,qr,y1,y2);
}
pair<int,pii> query(int x1,int x2,int y1,int y2){
    return query(1,1,n,1,x1,x2,y1,y2);
}
void solve(int l,int r){
    if(l==r) return;
    auto qwq=query(l,r-1,r,n);
    if(l!=1) qwq=min(qwq,query(1,l-1,l,r-1));
    auto [x,y]=qwq.se;
    if(l<=y&&y<r) swap(x,y);
    assert(l<=x&&x<r);
    TR[++Tcnt]=TREE{l,r,qwq.fi};
    solve(l,x); solve(x+1,r);
}
signed main(){
    // Fin("data.in");
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    For(_,1,m){
        int x,y,z; cin>>x>>y>>z; if(x>y) swap(x,y);
        if(x>1) Add(1,x-1,x,y-1,z);
        Add(x,y-1,y,n,z);
    }
    // STree::init(n); T[++QWQ].__reset(); build(1,1,n,1,QWQ);
    T.init(n); build(1,1,n,1,1);
    solve(1,n); assert(Tcnt==n-1); sort(TR+1,TR+n,[](TREE X,TREE Y){return X.z>Y.z;});
    static int fa[N],siz[N]; iota(fa+1,fa+1+n,1); For(i,1,n) siz[i]=1;
    function<int(int)> getfa=[&](int x) { return x==fa[x]?x:(fa[x]=getfa(fa[x])); };
    int ans=0; constexpr int mod=998244353;
    For(i,1,n-1){
        auto [x,y,z]=TR[i]; x=getfa(x); y=getfa(y);
        ans=(ans+1ll*siz[x]*siz[y]%mod*z)%mod; fa[y]=x; siz[x]+=siz[y];
    }
    debug(ans);
    cout<<(ans+1ll*n*(n-1)/2%mod*ll(2e9))%mod<<'\n';
    debug(T.TOT());
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: May 24 Fri, 16 : 06 : 47