#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 5, mod = 998244353;

inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
	return s * f;
}

typedef long long ll;

int u[N], v[N], n, m, f[N], siz[N];
ll w[N];
bool vis[N];
set<pair<ll, int> > conv;
set<pair<int, int> > e[N];

inline void del(int i) {
	conv.erase(make_pair(w[i], i));
	e[u[i]].erase(make_pair(v[i], i));
	e[v[i]].erase(make_pair(u[i], i));
}

inline int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; ++i) {
		u[i] = read(); v[i] = read(); w[i] = read();
		if (u[i] > v[i]) swap(u[i], v[i]);
		if (v[i] == u[i] + 1 || (v[i] == n && u[i] == 1)) conv.insert(make_pair(w[i], i));
		e[u[i]].insert(make_pair(v[i], i));
		e[v[i]].insert(make_pair(u[i], i));
	} int T = m - (n - 1);
	while (T--) {
		int x = conv.begin() -> second;
		del(x); vis[x] = 1;
		int now = u[x], lst = v[x];
		while (now != v[x]) {
			set<pair<int, int> > :: iterator it = e[now].upper_bound(make_pair(lst, 0x3f3f3f3f));
			if (it == e[now].end()) it = e[now].begin();
			int i = it -> second;
			if (conv.find(make_pair(w[i], i)) == conv.end()) {
				w[i] += w[x];
				conv.insert(make_pair(w[i], i));
				if (u[i] != now) swap(u[i], v[i]);
			} else {
				del(i);
				w[i] += w[x];
			} lst = now; now = it -> first;
		} 
	} for (int i = 1; i <= n; ++i) f[i] = i, siz[i] = 1;
	conv.clear(); int res = 0;
	for (int i = 1; i <= m; ++i)
		if (!vis[i]) conv.insert(make_pair(-w[i], i));
	for (pair<ll, int> i : conv) {
		int x = u[i.second], y = v[i.second];
		x = find(x); y = find(y);
		res += 1ll * (w[i.second] % mod) * (1ll * siz[x] * siz[y] % mod) % mod;
		if (res >= mod) res -= mod;
		f[x] = y; siz[y] += siz[x];
	} printf("%d\n", res); return 0;
}