#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
const int N = 20004, NN = N * 72;
int n, m, u, v, w, s[N], c[N], nodes, root[N], ls[NN], rs[NN], tag[NN], fa[N], siz[N];
pii tree[NN]; basic_string <pii> adj[N]; long long ans; 
struct E {
	int u, v, w;
	bool operator < (const E &e) const {
		return w > e. w;
	}
} edge[N];
pii operator + (const pii &a, const int &b) {
	return pii (a. first + b, a. second);
}
void pushup(int rt) {
	tree[rt] = min(tree[ls[rt]], tree[rs[rt]]) + tag[rt];
}
void push(int rt, int z) {
	tree[rt] = tree[rt] + z, tag[rt] += z;
}
void build(int &rt, int l, int r) {
	rt = ++ nodes;
	if (l == r) return void (tree[rt] = pii (c[l], l));
	int mid = l + r >> 1;
	build(ls[rt], l, mid), build(rs[rt], mid+1, r);
	pushup(rt);
}
void update(int lrt, int &rt, int l, int r, int x, int y, int z) {
	rt = ++ nodes, ls[rt] = ls[lrt], rs[rt] = rs[lrt], tree[rt] = tree[lrt], tag[rt] = tag[lrt];
	if (l == x && r == y) return push(rt, z);
	int mid = l + r >> 1;
	if (y <= mid) update(ls[lrt], ls[rt], l, mid, x, y, z);
	else if (x > mid) update(rs[lrt], rs[rt], mid+1, r, x, y, z);
	else update(ls[lrt], ls[rt], l, mid, x, mid, z), update(rs[lrt], rs[rt], mid+1, r, mid+1, y, z);
	pushup(rt);
}
pii query(int rt, int l, int r, int x, int y) {
	if (l == x && r == y) return tree[rt];
	int mid = l + r >> 1;
	if (y <= mid) return query(ls[rt], l, mid, x, y) + tag[rt];
	else if (x > mid) return query(rs[rt], mid+1, r, x, y) + tag[rt];
	else return min(query(ls[rt], l, mid, x, mid), query(rs[rt], mid+1, r, mid+1, y)) + tag[rt];
}
void solve(int u, int l, int r) {
	if (l > r) return ;
	pii c = min(pii (s[u], r + 1), l == r ? pii (s[r], r + 1) : r == n ? min(query(root[l], 1, n, l + 1, r), pii (:: c[l], r + 1)) : query(root[l], 1, n, l + 1, r + 1));
	edge[++m] = (E) {u, l, c. first}, solve(l, l + 1, c. second - 1), solve(u, c. second, r);
}
int find(int u) {
	return u == fa[u] ? u : fa[u] = find(fa[u]);
}
int main() {
	cin >> n >> m;
	for (int i=1; i<=m; i++)
		scanf ("%d%d%d", &u, &v, &w), adj[u] += pii (v, w), adj[v] += pii (u, w), s[u] += w, s[v] += w;
	for (int i=2; i<=n; i++) {
		c[i] = c[i-1];
		for (pii e : adj[i-1])
			c[i] += (e. first >= i ? 1 : - 1) * e. second;
	} build(root[1], 1, n);
	for (int i=2; i<=n; i++) {
		root[i] = root[i-1];
		int s = 0;
		for (pii e : adj[i-1]) {
			int j = e. first, w = e. second;
			if (j >= i) s += w, update(root[i], root[i], 1, n, i, j, - w << 1);
			else s -= w, update(root[i], root[i], 1, n, j + 1, i - 1, w << 1);
		} push(root[i], s);
	}
	pii c = query(root[1], 1, n, 2, n);
	edge[m=1] = (E) {1, n, c. first}, solve(1, 2, c. second - 1), solve(c. second, c. second + 1, n);
	for (int i=1; i<=n; i++)
		fa[i] = i, siz[i] = 1;
	sort (edge+1, edge+n);
	for (int i=1; i<n; i++) {
		int u = find(edge[i]. u), v = find(edge[i]. v);
		ans += 1ll * siz[u] * siz[v] * edge[i]. w, fa[v] = u, siz[u] += siz[v];
	} cout << (ans + 1000000000ll * n * (n - 1)) % 998244353;
}