// Skyqwq
#include <iostream>
#include <cstdio>
#include <cstring>
#define x first
#define y second
using namespace std;

typedef long long LL;
typedef pair<int, int> Poly;

const int N = 31, M = N * N, P = 998244353, S = 153000;

int n, m, U[M], V[M], W[M], f[S], mx, ans;

Poly a[N][N];

int inline power(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = (LL) res * a % P;
		a = (LL)a * a % P;
		b >>= 1;
	}
	return res;
}


Poly operator + (Poly a, Poly b) {
	return (Poly) { (a.x + b.x) % P, (a.y + b.y) % P };
}

Poly operator - (Poly a, Poly b) {
	return (Poly) { (a.x - b.x + P) % P, (a.y - b.y + P) % P };
}

Poly operator * (Poly a, Poly b) {
	return (Poly) { (LL)a.x * b.x % P, ((LL)a.x * b.y + (LL)a.y * b.x) % P };
}

Poly inline inv(Poly a) {
	int I = power(a.x, P - 2);
	return (Poly) { I, (P - (LL)a.y * I % P * I % P) % P };
}

Poly operator / (Poly a, Poly b) {
	return a * inv(b);
}

void inline add(int u, int v, int w) {
	Poly t = (Poly) { 1, w };
	a[u][u] = a[u][u] + t, a[v][v] = a[v][v] + t;
	a[u][v] = a[u][v] - t, a[v][u] = a[v][u] - t;
}


int inline det() {
	int f = 1;
	Poly res = (Poly) { 1, 0 };
	for (int i = 1; i <= n; i++) {
		if (!a[i][i].x) {
			for (int j = i + 1; j <= n; j++) {
				if (a[j][i].x) {
					f *= -1;
					swap(a[i], a[j]);
					break;
				}
			}
		}
		if (!a[i][i].x && !a[i][i].y) return 0;
		for (int j = i + 1; j <= n; j++) {
			Poly t = a[j][i] / a[i][i];
			for (int k = i; k <= n; k++)
				a[j][k] = a[j][k] - a[i][k] * t;
		}
		res = res * a[i][i];
	}
	return (res.y * f + P) % P;
}

int inline calc(int k) {
	memset(a, 0, sizeof a);
	int cnt = 0;
	for (int i = 1; i <= m; i++)
		if (W[i] % k == 0) cnt++, add(U[i], V[i], W[i]);
	if (cnt < n - 1) return 0;
	return det(); 
}

int main() {
	scanf("%d%d", &n, &m); --n;
	for (int i = 1; i <= m; i++) scanf("%d%d%d", U + i, V + i, W + i), mx = max(mx, W[i]);
	for (int i = 1; i <= mx; i++) f[i] = calc(i);
	for (int i = mx; i; i--) {
		for (int j = 2 * i; j <= mx; j += i) f[i] = (f[i] - f[j] + P) % P;
		ans = (ans + (LL)i * f[i]) % P;
	}
	printf("%d\n", ans);
	return 0;
}