#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define unsi unordered_set<int>
#define qi queue<int>
#define sti stack<int>
#define pqi priority_queue<int>
#define mii map<int,int>
#define unmii unordered_map<int,int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int N=30+5;
const int M=435+5;
const int V=152501+5;
const ll mod=998244353;
int n,m,mxv=0;
struct sdf{
    int u,v,w;
}eg[M];
vi v[V];
ll phi[V];bool ok[V];int p[V],cnt=0;
void init(){
	phi[1]=1;
	for (int i=2;i<=mxv;i++){
	    if (!ok[i]){
	        p[++cnt]=i;phi[i]=i-1;
        }
        for (int j=1;j<=cnt&&i*p[j]<=mxv;j++){
            ok[i*p[j]]=1;
            if (i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j]%mod;break;
            }
            phi[i*p[j]]=phi[i]*phi[p[j]]%mod;
        }
    }
}
ll fst(ll x,ll y){
    ll ans=1;
    while(y){
        if (y&1)ans=ans*x%mod;
        x=x*x%mod;y>>=1;
    }
    return ans;
}
struct poly{
    ll a,b;
    poly operator+(const poly&x){
        return {(a+x.a)%mod,(b+x.b)%mod};
    }
    poly operator-(const poly&x){
        return {(a-x.a+mod)%mod,(b-x.b+mod)%mod};
    }
    poly operator*(const poly&x){
        return {a*x.a%mod,(a*x.b+b*x.a)%mod};
    }
    poly operator/(const poly&x){
        ll inv=fst(x.a,mod-2);
        return {a*inv%mod,(inv*b%mod-a*x.b%mod+mod)%mod*inv%mod*inv%mod};
    }
};
poly a[N][N];
ll det(){
    bool sgn=0;
    for (int i=1;i<n;i++){
        int pos=0;
        for (int j=i;j<n;j++){
            if (a[i][j].a){
                pos=j;break;
            }
        }
        if (i!=pos)sgn^=1,swap(a[i],a[pos]);
        poly inv={1,0};inv=inv/a[i][i];
        for (int j=i+1;j<n;j++){
            poly bs=a[j][i]*inv;
            for (int k=i;k<n;k++){
                a[j][k]=a[j][k]-a[i][k]*bs;
            }
        }
    }
    poly ans={1,0};
    for (int i=1;i<n;i++)ans=ans*a[i][i];
    if (sgn)ans.b=mod-ans.b;
    return ans.b;
}
int main(){
	freopen ("haoi2020_count.in","r",stdin);
	freopen ("haoi2020_count.out","w",stdout);
	scanf("%d%d",&n,&m);
    if (m<n-1){
        printf("0\n");return 0;
    }
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&eg[i].u,&eg[i].v,&eg[i].w);
        int w=eg[i].w;mxv=max(mxv,w);
        for (int j=1;j*j<=w;j++){
            if (w%j)continue;
            v[j].pb(i);
            if (j*j!=w)v[w/j].pb(i);
        }
    }init();
    ll ans=0;
    for (int i=1;i<=mxv;i++){
        if (v[i].size()<n-1)continue;
        for (int j=1;j<=n;j++)for (int k=1;k<=n;k++)a[j][k]={0,0};
        for (int j=0;j<v[i].size();j++){
            int id=v[i][j];
            int u=eg[id].u,v=eg[id].v,w=eg[id].w;
            poly now={1,w};
            a[u][v]=a[u][v]-now;
            a[v][u]=a[v][u]-now;
            a[u][u]=a[u][u]+now;
            a[v][v]=a[v][v]+now;
        }
        ll now=det();
        ans=(ans+now*phi[i]%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}