#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mod = 998244353;

const int N = 2e5;
const int M = 4e5;

int n, m;
int u[M + 5], v[M + 5];
ll w[M + 5];
set<pair<int, int>> e[N + 5];
priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> pQ;
bool outer[M + 5];
vector<tuple<ll, int, int>> g;

void insert(int i) {
  e[u[i]].emplace((v[i] - u[i] + n) % n, i), e[v[i]].emplace((u[i] - v[i] + n) % n, i);
}
void erase(int i) {
  e[u[i]].erase(make_pair((v[i] - u[i] + n) % n, i)), e[v[i]].erase(make_pair((u[i] - v[i] + n) % n, i));
}

int ans;

struct UnionFind {
  int fa[N + 5], siz[N + 5];
  void init(int n) { fill_n(fa, n, -1), fill_n(siz, n, 1); }
  bool isRoot(int u) { return fa[u] == -1; }
  int find(int u) { return isRoot(u) ? u : fa[u] = find(fa[u]); }
  void merge(int u, int v, int w) {
    int fu = find(u), fv = find(v);
    if (fu == fv) return ;
    ans = (ans + (ll)w * siz[fu] % mod * siz[fv]) % mod,
    siz[fu] += siz[fv], fa[fv] = fu;
  }
} uf;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", u + i, v + i, w + i), --u[i], --v[i], insert(i);
    if ((v[i] - u[i] + n) % n == 1) pQ.emplace(w[i], i, u[i], v[i]), outer[i] = 1;
    else if ((u[i] - v[i] + n) % n == 1) pQ.emplace(w[i], i, v[i], u[i]), outer[i] = 1;
  }
  while (!pQ.empty()) {
    auto [_, i, s, t] = pQ.top(); pQ.pop();
    if (!outer[i]) continue;
    vector<tuple<int, int, int>> cyc; outer[i] = 0, erase(i);
    for (int p = s, q, len = (t - s + n) % n; p != t; p = q) {
      auto [l, j] = *e[p].upper_bound(make_pair(len, m));
      len = n - l, cyc.emplace_back(j, p, q = (p + l) % n), w[j] += w[i];
      if (outer[j] ^= 1) pQ.emplace(w[j], j, p, q);
      else erase(j), g.emplace_back(w[j], p, q);
    }
  }
  uf.init(n), sort(g.begin(), g.end(), greater<tuple<ll, int, int>>());
  for (auto [w, u, v] : g) uf.merge(u, v, w % mod);
  printf("%d\n", ans);
}