只对了 $m\leq n$ 和 $w_i$ 全部相同的点，难受

#include <bits/stdc++.h>
int n, m;
const int mod = 998244353;
#define mul(x, y) ((int)(1ll * x * y % (1ll * mod)))
#define add(x, y) (x + y >= mod ? x + y - mod : x + y)
#define minus(x, y) (x - y < 0 ? x - y + mod : x - y)
int phi[160005], p[160005], cnt = 0, is[160005];
int u[905], v[905], w[905];
struct fuck{
	int a, b;
}mat[35][35];
void clear(){
	memset(mat, 0, sizeof mat);
	return ;
}
inline int Qpow(int x, int y){
	int r = 1;
	while(y){
		if(y & 1) r = mul(r, x);
		x = mul(x, x);
		y >>= 1;
	}
	return r;
}
inline int inv(int x){
	return Qpow(x, mod - 2);
}
inline fuck operator * (fuck x, fuck y){
	fuck t;
	t.a = mul(x.a, y.b) + mul(x.b, y.a);
	t.a %= mod;
	t.b = mul(x.b, y.b);
	return t;
}
inline fuck operator / (fuck x, fuck y){
	fuck t;
	int id = inv(y.b);
	int id2 = mul(id, id);
	t.a = mul(x.a, y.b) - mul(y.a, x.b);
	if(t.a < 0) t.a += mod;
	t.a = mul(t.a, id2);
	t.b = mul(x.b, id);
	return t;
}
inline fuck operator + (fuck x, fuck y){
	fuck t;
	t.a = add(x.a, y.a);
	t.b = add(x.b, y.b);
	return t;
}
inline fuck operator - (fuck x, fuck y){
	fuck t;
	t.a = minus(x.a, y.a);
	t.b = minus(x.b, y.b);
	return t;
}
void Euler(){
	memset(is, 1, sizeof is);
	is[1] = 0;
	phi[1] = 1;
	for(int i = 2; i <= 152501; ++i){
		if(is[i]) p[++cnt] = i, phi[i] = i - 1;
		for(int j = 1; j <= cnt && i * p[j] <= 152501; ++j){
			is[i * p[j]] = 0;
			if(i % p[j]){
				phi[i * p[j]] = phi[i] * (p[j] - 1);
			} 
			else {
				phi[i * p[j]] = phi[i] * p[j];
				break;
			}
		}
	}
	return ;
}
int nzero(fuck t){
	return t.a || t.b;
}
int Gauss(){
	int flag = 1;
	for(int i = 1; i <= n - 1; ++i){
		int gg = 0;
		for(int j = i; j <= n - 1; ++j){
			if(nzero(mat[j][i])){
				std::swap(mat[j], mat[i]);
				gg = 1;
				if(i != j) flag *= -1;
			}
		}
		if(!gg) return 0;
		for(int j = i + 1; j <= n - 1; ++j){
			fuck s = mat[j][i] / mat[i][i];
			for(int k = i; k <= n - 1; ++k){
				mat[j][k] = mat[j][k] - mat[i][k] * s;
			}
		}
	}
	fuck ans;
	ans.a = 0, ans.b = 1;
	for(int i = 1; i <= n - 1; ++i) ans = ans * mat[i][i];
	if(flag == 1) return ans.a;
	else return (mod - ans.a) % mod;
}
signed main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i){
		scanf("%d%d%d", &u[i], &v[i], &w[i]);
	}
	Euler();
	int Ans = 0, Cnt = 0;
	for(int i = 1; i <= 152501; ++i){
		Cnt = 0;
		for(int j = 1; j <= m; ++j){
			if(w[j] % i) continue;
			++Cnt;
		}
		if(Cnt < n - 1) continue;
		clear();
		for(int j = 1; j <= m; ++j){
			if(w[j] % i) continue;
			int U = u[j] - 1, V = v[j] - 1;
			fuck t;
			t.a = w[j], t.b = 1;
			mat[U][U] = mat[U][U] + t;
			mat[V][V] = mat[V][V] + t;
			mat[U][V] = mat[U][V] - t;
			mat[V][U] = mat[V][U] - t; 
		}
		for(int j = 1; j <= n - 1; ++j){
			for(int k = 1; k <= n - 1; ++k){
				if(mat[j][k].a < 0) mat[j][k].a += mod;
				if(mat[j][k].b < 0) mat[j][k].b += mod;
			}
		}
		int g = Gauss();
		Ans += mul(g, phi[i]);
		Ans %= mod;
	}
	printf("%d\n", Ans);
	return 0;
}