#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct val
{
    int tm, ps, v;
    bool operator < (const val i) const { return v < i.v; }
    val operator + (const val i) const { return {i.tm, ps, v + i.v}; }
};
struct node
{
    val mn, hm, lz, lm; int lc, rc; 
    void add(const val tg, const val tm) { hm = min(hm, mn + tm); lm = min(lm, lz + tm); mn = mn + tg; lz = lz + tg; }
} t[int(1e7)];

#define ls t[p].lc
#define rs t[p].rc
typedef const int ci;
void pushup(ci p) { t[p].mn = min(t[ls].mn, t[rs].mn); t[p].hm = min(t[ls].hm, t[rs].hm); }
void pushdown(ci p)
{
    if (t[p].lz.t) t[ls].add(t[p].lz, t[p].lm), t[rs].add(t[p].lz, t[p].lm);
    t[p].lz = t[p].lm = {0, 0, 0};
}
int a, n, f[20002], s[20002], rl[20002], rr[20002];
void build(int &p, ci l, ci r)
{
    p = ++a; t[p].mn = t[p].hm = {0, l, (int)2e8}; if (l == r) return;
    ci m(l + r >> 1); build(ls, l, m); build(rs, m + 1, r);
}
void modify(ci p, ci l, ci r, ci ql, ci qr, const val w)
{
    if (ql <= l && r <= qr) { t[p].add(w, w); return; } 
    t[++a] = t[ls]; ls = a; t[++a] = t[rs]; rs = a;
    pushdown(p); ci m(l + r >> 1);
    if (ql <= m) modify(ls, l, m, ql, qr, w);
    if (qr > m) modify(rs, m + 1, r, ql, qr, w);
    pushup(p);
}
val query(ci p, ci l, ci r, ci ql, ci qr, val tg, val tm)
{
    if (ql <= l && r <= qr) return min(t[p].hm, t[p].mn + tm);
    if (!tg.t) tg = t[p].lz, tm = t[p].lm;
    else tm = min(t[p].lm, t[p].lz + tm), tg = t[p].lz + tg;
    ci m(l + r >> 1); val w({0, 0, (int)2e8});
    if (ql <= m) w = min(w, query(ls, l, m, ql, qr, tg, tm));
    if (qr > m) w = min(w, query(rs, m + 1, r, ql, qr, tg, tm));
    return w;
}

struct square { int L, R, X, Y, W; }; vector<square> b;
vector<tuple<int, int, int>> e, d[20002], g[20002];
val calc(ci u, ci v)
{
    val wl(query(rl[u], 1, n, u, v - 1, {0, 0, 0}, {0, 0, 0})),
        wr(query(rr[v], 1, n, u + 1, v, {0, 0, 0}, {0, 0, 0}));
    swap(wr.tm, wr.ps); return min(wl, wr);
}
void construct(ci l, ci r)
{
    if (l == r) return;
    val w(calc(l, r)); e.push_back({w.v, l, r});
    if (w.tm <= l && l <= w.ps) construct(l, w.ps), construct(w.ps + 1, r);
    else                        construct(l, w.tm - 1), construct(w.tm, r);
}

int find(ci p) { return p != f[p] ? f[p] = find(f[p]) : p; }
int main()
{
    int m; long long h(0); scanf("%d%d", &n, &m);
    while (m--)
    {
        int u, v, w; scanf("%d%d%d", &u, &v, &w); if (u > v) swap(u, v);
        b.push_back({u + 1, v, v, n, w}); b.push_back({1, u, u, v - 1, w});
    }
    build(rl[0], 1, n); g[1].push_back({1, n, 2e8});
    for (auto [L, R, X, Y, W] : b) d[L].push_back({X, Y, W}), g[R + 1].push_back({X, Y, W});
    for (int i(1); i <= n; ++i)
    {
        rl[i] = rl[i - 1];
        for (auto [l, r, w] : d[i]) t[++a] = t[rl[i]], rl[i] = a, modify(a, 1, n, l, r, {i, 0,  w});
        for (auto [l, r, w] : g[i]) t[++a] = t[rl[i]], rl[i] = a, modify(a, 1, n, l, r, {i, 0, -w});
    }
    for (int i(0); i < n + 2; ++i) d[i].clear(), g[i].clear();
    build(rr[n + 1], 1, n); g[n].push_back({1, n, 2e8});
    for (auto [L, R, X, Y, W] : b) d[Y].push_back({L, R, W}), g[X - 1].push_back({L, R, W});
    for (int i(n); i; --i)
    {
        rr[i] = rr[i + 1];
        for (auto [l, r, w] : d[i]) t[++a] = t[rr[i]], rr[i] = a, modify(a, 1, n, l, r, {i, 0,  w});
        for (auto [l, r, w] : g[i]) t[++a] = t[rr[i]], rr[i] = a, modify(a, 1, n, l, r, {i, 0, -w});
    }

    construct(1, n); sort(begin(e), end(e), greater<tuple<int, int, int>>()); 
    for (int i(1); i <= n; ++i) f[i] = i, s[i] = 1;
    for (auto [w, u, v] : e)
    {
        h += (long long)w * s[find(u)] * s[find(v)];
        s[f[v]] += s[f[u]]; f[f[u]] = f[v];
    }
    return !printf("%d\n", (h + (long long)n * (n - 1) * int(1e9)) % 998244353);
}

answer.code: In function ‘void pushdown(ci)’:
answer.code:23:17: error: ‘struct val’ has no member named ‘t’; did you mean ‘tm’?
   23 |     if (t[p].lz.t) t[ls].add(t[p].lz, t[p].lm), t[rs].add(t[p].lz, t[p].lm);
      |                 ^
      |                 tm
answer.code: In function ‘val query(ci, ci, ci, ci, ci, val, val)’:
answer.code:44:13: error: ‘struct val’ has no member named ‘t’; did you mean ‘tm’?
   44 |     if (!tg.t) tg = t[p].lz, tm = t[p].lm;
      |             ^
      |             tm
answer.code: In function ‘int main()’:
answer.code:102:22: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
  102 |     return !printf("%d\n", (h + (long long)n * (n - 1) * int(1e9)) % 998244353);
      |                     ~^     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                      |                                             |
      |                      int                                           long long int
      |                     %lld
answer.code:71:33: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |     int m; long long h(0); scanf("%d%d", &n, &m);
      |                            ~~~~~^~~~~~~~~~~~~~~~
answer.code:74:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   74 |         int u, v, w; scanf("%d%d%d", &u, &v, &w); if (u > v) swap(u, v);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~