#include <bits/stdc++.h>

using namespace std;
using lint = long long;
const int N = 4e5 + 7, inf = 1e9, mod = 998244353;

struct pli {
	lint first, second;
	bool operator < (const pli &p) const {
		return first != p.first ? first < p.first : second < p.second;
	}
};

int grp[N], siz[N];
int find(int x) {
	return grp[x] == x ? x : grp[x] = find(grp[x]);
}

set<pli> cov, E[N];
int x[N], y[N], rem[N];
lint w[N];

void del(int e) {
	cov.erase({w[e], e});
	E[x[e]].erase({y[e], e});
	E[y[e]].erase({x[e], e});
	// cerr << "Del E " << e << ": " << x[e] << " - " << y[e] << " (" << w[e] << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> x[i] >> y[i] >> w[i];
		if (x[i] > y[i]) swap(x[i], y[i]);
		if (x[i] + 1 == y[i] || (x[i] == 1 && y[i] == n)) cov.insert({w[i], i});
		if (x[i] == 1 && y[i] == n) swap(x[i], y[i]);
		E[x[i]].insert({y[i], i}), E[y[i]].insert({x[i], i});
	}

	int T = m - (n - 1);
	while (T--) {
		int e = cov.begin()->second;
		// cerr << "Pop E " << e << " !\n";
		del(e), rem[e] = 1;
		int cur = x[e], prv = y[e];
		while (cur != y[e]) {
			auto it = E[cur].upper_bound({prv, inf}); // 顺时针遍历
			if (it == E[cur].end()) it = E[cur].begin();
			int i = it->second;
			prv = cur, cur = it->first;
			// cerr << "Nxt E " << i << '\n';
			if (cov.find({w[i], i}) == cov.end()) {
				w[i] += w[e];
				cov.insert({w[i], i});
				if (x[i] != cur) swap(x[i], y[i]); // 修改方向
				// cerr << "Make IN " << i << ": " << x[i] << " - " << y[i] << '\n';
			} else {
				del(i);
				w[i] += w[e];
			}

			// cerr << "Cur to " << cur << " prv " << prv << '\n';
		}
	}

	cov.clear();
	for (int i = 1; i <= m; ++i) {
		if (!rem[i]) cov.insert({-w[i], i});
	}

	for (int i = 1; i <= n; ++i) grp[i] = i, siz[i] = 1;
	int ans = 0;
	for (auto it : cov) {
		int e = it.second;
		// cerr << "Rest e " << e << ": " << x[e] << ", " << e[y] << " (" << w[e] << '\n';
		int u = find(x[e]), v = find(y[e]);
		if (u == v) continue;
		ans = (ans + 1ll * w[e] % mod * siz[u] % mod * siz[v]) % mod;
		grp[u] = v, siz[v] += siz[u];
	} cout << ans << '\n';
}