#include<iostream>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
using LL = long long;
const int mod = 998244353;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

int mul(int a, int b){
    return 1LL * a * b % mod;
}

int a[30][30];

int det(int n){
    if (n == 0) return 0;
    int ans = 1;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            int x = i, y = j;
            while(a[x][i]){
                int t = a[y][i] / a[x][i];
                for(int k = i; k < n; k++){
                    sub(a[y][k], mul(t, a[x][k]));
                }
                swap(x, y);
            }
            if (x == i){
                swap(a[i], a[j]);
                ans = (mod - ans) % mod;
            }
        }
        if (a[i][i] == 0) return 0;
        ans = mul(ans, a[i][i]);
    }
    return ans;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const int N = 152501;
    vector<vector<int> > factor(N + 1);
    for(int i = 1; i <= N; i++){
        for(int j = i; j <= N; j += i){
            factor[j].push_back(i);
        }
    }
    int n, m;
    cin >> n >> m;
    vector<vector<array<int, 3> > > edge(N + 1);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        if (a > b) swap(a, b);
        for(auto x : factor[c]){
            edge[x].push_back({a, b, c});
        }
    }
    int ans = 0;
    vector<int> f(N + 1);
    for(int i = N; i >= 1; i--){
        if (edge[i].size() < n - 1) continue;
        
        for(auto [u, v, w] : edge[i]){

            auto get = [&](int x){
                if (x == v) return u;
                if (x < v) return x;
                return x - 1;
            };

            memset(a, 0, sizeof a);
            for(auto [uu, vv, _] : edge[i]){
                if (uu == u and vv == v) continue;
                uu = get(uu);
                vv = get(vv);
                a[uu][uu] += 1;
                a[vv][vv] += 1;
                a[uu][vv] -= 1;
                a[vv][uu] -= 1;
            }
            add(f[i], mul(w, det(n - 2)));
        }
        add(ans, mul(f[i], i));
        for(auto x : factor[i]){
            sub(f[x], f[i]);
        }
    }
    cout << ans << '\n';

}