分析
显然莫比乌斯反演一下，可以得到
$$
\sum_{d=1}^{+\infty}\varphi(d)\sum_{T:\forall e\in T,d|w_e}\sum_{e\in T}w_e
$$
考虑如何快速求后面的东西，即所有边权是 $d$ 的倍数的边的所有生成树的边权和之和。
考虑矩阵树定理，将每条边的贡献设为 $wx+1$，划去一行一列后求行列式，一次项系数则为答案。感性理解：对于每条边，它的一次项都会和别的边的常数项求一次行列式算到答案里。
由于我们只需要求一次项系数所以可以对 $x^2$ 取模，则有
$$
\begin{aligned}
(ax+b)+(cx+d)&=(a+c)x+(b+d)\\
(ax+b)-(cx+d)&=(a-c)x+(b-d)\\
(ax+b)(cx+d)&\equiv(ad+bc)x+bd\pmod{x^2}\\
\frac{ax+b}{cx+d}&\equiv\frac{ad-bc}{d^2}x+\frac{b}{d}\pmod{x^2}\\
\end{aligned}
$$
第四个可以考虑手动多项式求逆。
设 $(c'x+d')(cx+d)\equiv 1\pmod{x^2}$，显然有 $d'=\frac{1}{d}$，然后 $c'd+d'c=0\Rightarrow c'=-\frac{c}{d^2}$。
这样子就有
$$
\frac{ax+b}{cx+d}\equiv(ax+b)(c'x+d')\equiv\frac{ad-bc}{d^2}x+\frac{b}{d}\pmod{x^2}
$$
直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。
另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=30+10,L=152501+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
return c;
}
int n,m,cnt[L];
struct edge { int u,v,w; } e[N*N];
int p[L],v[L],phi[L],pcnt=0;
void sieve(int n) {
phi[1]=1;
for (int i=2;i<=n;++i) {
if (!v[i]) p[++pcnt]=i,phi[i]=i-1;
for (int j=1;j<=pcnt&&i*p[j]<=n;++j) {
v[i*p[j]]=1;
if (i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);
else { phi[i*p[j]]=phi[i]*p[j]; break; }
}
}
}
struct poly {
int a,b;
poly(int a_=0,int b_=0): a(a_),b(b_) { }
}; // ax+b
poly operator +(poly x,poly y) {
return poly((x.a+y.a)%mod,(x.b+y.b)%mod);
}
poly operator -(poly x,poly y) {
return poly((x.a-y.a+mod)%mod,(x.b-y.b+mod)%mod);
}
poly operator *(poly x,poly y) {
return poly((1ll*x.a*y.b+1ll*x.b*y.a)%mod,1ll*x.b*y.b%mod);
}
poly operator /(poly x,poly y) {
int inv=qpow(y.b,mod-2);
return poly((1ll*x.a*y.b%mod-1ll*x.b*y.a%mod+mod)*inv%mod*inv%mod,1ll*x.b*inv%mod);
}
poly& operator +=(poly& x,poly y) { return x=x+y; }
poly& operator -=(poly& x,poly y) { return x=x-y; }
poly& operator *=(poly& x,poly y) { return x=x*y; }
poly& operator /=(poly& x,poly y) { return x=x/y; }
poly C[N][N];
poly Gauss(int n) {
poly ans(0,1);
for (int i=1;i<=n;++i) {
poly inv=poly(0,1)/C[i][i];
for (int j=i+1;j<=n;++j) {
poly t=C[j][i]*inv;
for (int k=i;k<=n;++k) C[j][k]-=C[i][k]*t;
}
}
for (int i=1;i<=n;++i) ans*=C[i][i];
return ans;
}
int calc(int d) {
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j) C[i][j]=poly();
for (int i=1;i<=m;++i) {
int u=e[i].u,v=e[i].v,w=e[i].w;
if (w%d) continue;
C[u][u]+=poly(w,1),C[v][v]+=poly(w,1);
C[u][v]-=poly(w,1),C[v][u]-=poly(w,1);
}
return Gauss(n-1).a;
}
int main() { sieve(152501);
n=read(),m=read();
for (int i=1;i<=m;++i) e[i]=(edge){read(),read(),read()};
for (int i=1;i<=m;++i)
for (int j=1;j*j<=e[i].w;++j) {
if (e[i].w%j) continue;
++cnt[j]; if (j*j!=e[i].w) ++cnt[e[i].w/j];
}
int ans=0;
for (int i=1;i<=152501;++i) {
if (cnt[i]<n-1) continue;
ans=(ans+1ll*phi[i]*calc(i))%mod;
}
printf("%d\n",ans);
return 0;
}