#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <valarray>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &x : v)
    is >> x;
  return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const uint Mod = 998244353;

constexpr uint norm(uint v) { return v >= Mod ? v - Mod : v; }

struct Z {
  uint v;

  constexpr Z(uint v = 0) : v(v) {}

  inline constexpr Z operator+(const Z &rhs) const { return norm(v + rhs.v); }

  inline constexpr Z operator-(const Z &rhs) const { return norm(v + Mod - rhs.v); }

  inline constexpr Z operator-() const { return norm(Mod - v); }

  inline constexpr Z operator*(const Z &rhs) const { return static_cast<ull>(v) * rhs.v % Mod; }

  inline constexpr Z inv() const;

  inline constexpr Z operator/(const Z &rhs) const { return *this * rhs.inv(); }

  constexpr operator uint() const { return v; }
};

inline constexpr Z &operator+=(Z &lhs, const Z &rhs) { return lhs = lhs + rhs; }

inline constexpr Z &operator-=(Z &lhs, const Z &rhs) { return lhs = lhs - rhs; }

inline constexpr Z &operator*=(Z &lhs, const Z &rhs) { return lhs = lhs * rhs; }

inline constexpr Z &operator/=(Z &lhs, const Z &rhs) { return lhs = lhs / rhs; }

inline constexpr Z pow(Z base, uint exp) {
  Z res = 1;
  for (; exp; base *= base, exp >>= 1)
    if (exp & 1)
      res *= base;
  return res;
}

inline constexpr Z Z::inv() const { return pow(*this, Mod - 2); }

const int N = 30, M = 500, W = 153005;

static uniform_int_distribution<> uid0(0, (int) Mod), uid1(1, (int) Mod);

struct Trunc {
  Z a, b;

  Trunc() {}

  Trunc(Z a, Z b) : a(a), b(b) {}

  Trunc operator+(const Trunc &rhs) const { return Trunc(a + rhs.a, b + rhs.b); }

  Trunc operator-(const Trunc &rhs) const { return Trunc(a - rhs.a, b - rhs.b); }

  Trunc operator-() const { return Trunc(-a, -b); }

  Trunc operator*(const Trunc &rhs) const {
    return Trunc(a * rhs.a, Z((static_cast<ull>(b.v) * rhs.a.v + static_cast<ull>(a.v) * rhs.b.v) % Mod));
  }

  int deg() const {
    if (a.v) return 0;
    if (b.v) return 1;
    return 2;
  }

  Trunc shift(int d) const {
    if (d == 0) return *this;
    return Trunc(0, a);
  }

  Trunc inv() const {
    Trunc nv = Trunc();
    nv.a = a.inv();
    nv.b = -b * nv.a * nv.a;
    return nv;
  }

  template<class URNG>
  static Trunc rand(URNG &g) {
    return Trunc({Z(uid1(g)), Z(uid0(g))});
  }
};

inline Trunc &operator+=(Trunc &lhs, const Trunc &rhs) { return lhs = lhs + rhs; }

inline Trunc &operator-=(Trunc &lhs, const Trunc &rhs) { return lhs = lhs - rhs; }

inline Trunc &operator*=(Trunc &lhs, const Trunc &rhs) { return lhs = lhs * rhs; }

int n, m;
int u[M], v[M], w[M];
int edc[W], phi[W];

int f[N];

int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

int tries;

const int LIMIT = 30;
int act;

namespace Kirkhoff {

  int adj[N][N];
  Trunc mat[N][N];

  // works when #SpanningTrees % p != 0
  vector<Trunc> BM(const vector<Trunc> &a) {
    vector<Trunc> rec = {Trunc({Z(1), Z(0)})}, crec = {Trunc({Z(1), Z(0)})};
    int l = 0;
    for (int r = 1; r <= a.size(); ++r) {
      Trunc v = Trunc();
      for (int i = 0; i < rec.size(); ++i) v += rec[i] * a[r - 1 - i];
      crec.insert(crec.begin(), Trunc());
      if (v.deg() < 2) {
        assert(v.deg() == 0);
        vector<Trunc> t = rec;
        if (crec.size() > t.size()) t.resize(crec.size());
        for (int i = 0; i < crec.size(); ++i)
          t[i] -= v * crec[i];
        if (l * 2 <= r - 1) {
          crec = rec;
          Trunc nv = v.inv();
          for (int i = 0; i < crec.size(); ++i)
            crec[i] *= nv;
          l = r - l;
        }
        swap(rec, t);
      }
    }
    return rec;
  }

  Trunc diag[N], row[N], col[N];
  int si[N * N], sj[N * N];
  Trunc sw[N * N];

  Trunc sparseDet(int n) {
    ++act;
    while (true) {
      ++tries;
      Trunc val = Trunc({Z(1), Z(0)});
      for (int i = 0; i < n; ++i) {
        diag[i] = Trunc::rand(rng);
        val *= diag[i];
        row[i] = Trunc::rand(rng);
        col[i] = Trunc::rand(rng);
      }
      int tot = 0;
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          if (mat[i][j].deg() == 0) {
            si[tot] = i;
            sj[tot] = j;
            sw[tot] = mat[i][j] * diag[i];
            ++tot;
          }
      vector<Trunc> vec;
      for (int i = 0; i <= n * 2; ++i) {
        static Trunc tmp[N];
        fill(tmp, tmp + n, Trunc());
        for (int j = 0; j < tot; ++j)
          tmp[sj[j]] += row[si[j]] * sw[j];
        vec.push_back(inner_product(tmp, tmp + n, col, Trunc()));
        //cerr << vec.back().a << ' ' << vec.back().b << " | ";
        copy(tmp, tmp + n, row);
      }
      //cerr << '\n';
      auto rec = BM(vec);
      //cerr << rec.size() << '\n';
      if (rec.size() == n + 1) {
        Trunc eigen = rec.back();
        if (n & 1) eigen = -eigen;
        return eigen * val.inv();
      }
    }
  }

  Trunc det(int n) {
    Trunc ret = Trunc({Z(1), Z(0)});
    for (int i = 0; i < n; ++i) {
      int lowest = mat[i][i].deg(), pref = i;
      for (int j = i + 1; j < n; ++j) {
        if (lowest > mat[i][j].deg()) {
          lowest = mat[i][j].deg();
          pref = j;
        }
      }
      if (pref != i) {
        for (int j = i; j < n; ++j)
          swap(mat[i][j], mat[pref][j]);
        ret = -ret;
      }
      if (lowest + ret.deg() >= 2) return Trunc();
      ret *= mat[i][i];
      Trunc nv = Trunc();
      if (lowest == 0) {
        nv = mat[i][i].inv();
      } else
        nv.a = mat[i][i].b.inv();
      for (int j = i; j < n; ++j)
        mat[i][j] *= nv;
      for (int j = i + 1; j < n; ++j)
        for (int k = n - 1; k >= i; --k)
          mat[j][k] -= (mat[i][k] * mat[j][i]).shift(mat[j][i].deg() - lowest);
    }
    return ret;
  }

  Z solve() {
    for (int i = 0; i < n; ++i)
      fill(mat[i], mat[i] + n, Trunc());
    int cnt = 0;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (adj[i][j]) {
          Trunc e = Trunc({Z(1), Z(adj[i][j])});
          mat[i][i] += e;
          mat[j][j] += e;
          mat[i][j] -= e;
          mat[j][i] -= e;
          ++cnt;
        }
    Z ret = (cnt >= LIMIT ? det(n - 1) : sparseDet(n - 1)).b;
    return ret;
  }

}

unordered_map<bitset<M>, Z> memo;

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> u[i] >> v[i] >> w[i];
    --u[i];
    --v[i];
    ++edc[w[i]];
  }
  iota(phi, phi + W, 0);
  Z ans = 0;
  int cnt = 0;
  for (int i = 1; i < W; ++i) {
    for (int j = i + i; j < W; j += i) {
      edc[i] += edc[j];
      phi[j] -= phi[i];
    }
    if (edc[i] < n - 1) continue;
    iota(f, f + n, 0);
    memset(Kirkhoff::adj, 0, sizeof(Kirkhoff::adj));
    int con = n;
    static bitset<M> edv;
    edv.reset();
    for (int j = 0; j < m; ++j)
      if (w[j] % i == 0) {
        edv.set(j);
        Kirkhoff::adj[u[j]][v[j]] = w[j];
        int x = find(u[j]), y = find(v[j]);
        if (x != y) {
          --con;
          f[y] = x;
        }
      }
    if (con != 1) continue;
    auto it = memo.find(edv);
    if (it != memo.end()) {
      ans += it->second * Z(phi[i]);
      continue;
    }
    ++cnt;
    Z th = Kirkhoff::solve();
    ans += th * Z(phi[i]);
    memo.insert(make_pair(edv, th));
  }
  cerr << "total dets: " << cnt << '\n';
  cerr << "average attempts: " << (double)tries / act << '\n';
  cout << ans << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}