// N 頂点M辺のグラフが与えられる
// 辺には重みw_iが割り振られている
// 全域木の重みを (重みの和) * (重みのgcd) と定義する
// 全ての全域木についての重みの和を求めて
// mod 998244353
//
// 2 <= N <= 30
// 1 <= w_i <= 152501
// 多重辺、自己ループ無し

fn main() {
    let (n, e) = read();
    let m = e.iter().map(|e| e.2).max().unwrap();
    let mut phi = (0..=m).collect::<Vec<_>>();
    for i in 2..=m {
        if i == phi[i] {
            for j in (1..=(m / i)).rev() {
                phi[j * i] -= phi[j];
            }
        }
    }
    let mut ans = M::zero();
    for (i, phi) in phi.iter().enumerate().skip(1) {
        let mut cnt = 0;
        let mut mat = vec![vec![Dual::new(M::zero(), M::zero()); n]; n];
        for &(a, b, w) in e.iter() {
            if w % i == 0 {
                cnt += 1;
                let v = Dual::new(M::one(), M::from(w));
                mat[a][a] = mat[a][a] + v;
                mat[b][b] = mat[b][b] + v;
                mat[a][b] = mat[a][b] - v;
                mat[b][a] = mat[b][a] - v;
            }
        }
        if cnt < n - 1 {
            continue;
        }
        for m in mat.iter_mut() {
            m.pop();
        }
        mat.pop();
        let det = determinant(mat).1;
        ans += M::from(*phi) * det;
    }
    println!("{}", ans);
}

// ---------- begin Dual ----------
#[derive(Clone, Copy, Default)]
pub struct Dual<T>(T, T);

impl<T> Dual<T> {
    pub fn new(a: T, b: T) -> Self {
        Self(a, b)
    }
}

impl<T> Zero for Dual<T>
where
    T: Zero,
{
    fn zero() -> Self {
        Self::new(T::zero(), T::zero())
    }
    fn is_zero(&self) -> bool {
        self.0.is_zero()
    }
}

impl<T> One for Dual<T>
where
    T: One + Zero + Clone,
{
    fn one() -> Self {
        Self::new(T::one(), T::zero())
    }
}

impl<T> Ring for Dual<T> where T: One + Zero + Clone + Sub<Output = T> {}
impl<T> Field for Dual<T> where T: One + Zero + Clone + Sub<Output = T> + Div<Output = T> {}

impl<T> Add for Dual<T>
where
    T: Add<Output = T>,
{
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Self::new(self.0 + rhs.0, self.1 + rhs.1)
    }
}

impl<T> Sub for Dual<T>
where
    T: Sub<Output = T>,
{
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        Self::new(self.0 - rhs.0, self.1 - rhs.1)
    }
}

impl<T> Mul for Dual<T>
where
    T: Clone + Add<Output = T> + Mul<Output = T>,
{
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        Self::new(
            self.0.clone() * rhs.0.clone(),
            self.0 * rhs.1 + self.1 * rhs.0,
        )
    }
}

impl<T> Div for Dual<T>
where
    T: Clone + One + Zero + Sub<Output = T> + Div<Output = T>,
{
    type Output = Self;
    fn div(self, rhs: Self) -> Self {
        assert!(!rhs.0.is_zero());
        let x = T::one() / rhs.0;
        let y = T::zero() - x.clone() * x.clone() * rhs.1;
        self * Self::new(x, y)
    }
}
// ---------- end Dual ----------

fn read() -> (usize, Vec<(usize, usize, usize)>) {
    let mut s = String::new();
    use std::io::*;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::<usize>());
    let mut next = || it.next().unwrap();
    let n = next();
    let m = next();
    let e = (0..m)
        .map(|_| {
            let a = next() - 1;
            let b = next() - 1;
            let c = next();
            (a, b, c)
        })
        .collect();
    (n, e)
}

pub fn determinant<T>(mut mat: Vec<Vec<T>>) -> T
where
    T: Field + Copy,
{
    let n = mat.len();
    assert!(mat.iter().all(|mat| mat.len() == n));
    let mut det = T::one();
    for i in (0..n).rev() {
        if let Some(x) = mat.iter().position(|mat| !mat[i].is_zero()) {
            if i != x {
                mat.swap(i, x);
                det = det * (T::zero() - T::one());
            }
            let mut a = mat.pop().unwrap();
            det = det * a[i];
            let inv = T::one() / a[i];
            a[..i].iter_mut().for_each(|a| *a = *a * inv);
            for mat in mat.iter_mut() {
                let mul = mat[i];
                for (mat, a) in mat.iter_mut().zip(a.iter()).take(i) {
                    *mat = *mat - mul * *a;
                }
            }
        } else {
            return T::zero();
        }
    }
    det
}

pub trait Zero: Sized + Add<Self, Output = Self> {
    fn zero() -> Self;
    fn is_zero(&self) -> bool;
}

pub trait One: Sized + Mul<Self, Output = Self> {
    fn one() -> Self;
}

pub trait Ring: Zero + One + Sub<Self, Output = Self> {}
pub trait Field: Ring + Div<Self, Output = Self> {}

impl<T: Modulo> Zero for ModInt<T> {
    fn zero() -> Self {
        Self::zero()
    }
    fn is_zero(&self) -> bool {
        self.is_zero()
    }
}

impl<T: Modulo> One for ModInt<T> {
    fn one() -> Self {
        Self::one()
    }
}

impl<T: Modulo> Ring for ModInt<T> {}
impl<T: Modulo> Field for ModInt<T> {}

pub const fn pow_mod(mut r: u32, mut n: u32, m: u32) -> u32 {
    let mut t = 1;
    while n > 0 {
        if n & 1 == 1 {
            t = (t as u64 * r as u64 % m as u64) as u32;
        }
        r = (r as u64 * r as u64 % m as u64) as u32;
        n >>= 1;
    }
    t
}

pub const fn primitive_root(p: u32) -> u32 {
    let mut m = p - 1;
    let mut f = [1; 30];
    let mut k = 0;
    let mut d = 2;
    while d * d <= m {
        if m % d == 0 {
            f[k] = d;
            k += 1;
        }
        while m % d == 0 {
            m /= d;
        }
        d += 1;
    }
    if m > 1 {
        f[k] = m;
        k += 1;
    }
    let mut g = 1;
    while g < p {
        let mut ok = true;
        let mut i = 0;
        while i < k {
            ok &= pow_mod(g, (p - 1) / f[i], p) > 1;
            i += 1;
        }
        if ok {
            break;
        }
        g += 1;
    }
    g
}

pub const fn is_prime(n: u32) -> bool {
    if n <= 1 {
        return false;
    }
    let mut d = 2;
    while d * d <= n {
        if n % d == 0 {
            return false;
        }
        d += 1;
    }
    true
}

use std::marker::*;
use std::ops::*;

pub trait Modulo {
    fn modulo() -> u32;
    fn build(v: u32) -> u32;
    fn reduce(v: u64) -> u32;
}

pub struct ConstantModulo<const M: u32>;

impl<const M: u32> ConstantModulo<{ M }> {
    const ORDER: usize = (M - 1).trailing_zeros() as usize;
    const PRIMITIVE_ROOT: u32 = primitive_root(M);
    const ZETA: u32 = pow_mod(Self::PRIMITIVE_ROOT, (M - 1) >> Self::ORDER, M);
    const REM: u32 = {
        let mut t = 1u32;
        let mut s = !M + 1;
        let mut n = !0u32 >> 2;
        while n > 0 {
            if n & 1 == 1 {
                t = t.wrapping_mul(s);
            }
            s = s.wrapping_mul(s);
            n >>= 1;
        }
        t
    };
    const INI: u64 = ((1u128 << 64) % M as u128) as u64;
    const IS_PRIME: () = assert!(is_prime(M));
}

impl<const M: u32> Modulo for ConstantModulo<{ M }> {
    fn modulo() -> u32 {
        M
    }
    fn build(v: u32) -> u32 {
        Self::reduce(v as u64 * Self::INI)
    }
    fn reduce(x: u64) -> u32 {
        debug_assert!(x < (Self::modulo() as u64) << 32);
        let b = (x as u32 * Self::REM) as u64;
        let t = x + b * M as u64;
        let mut c = (t >> 32) as u32;
        if c >= M {
            c -= M;
        }
        c as u32
    }
}

pub trait NTTFriendly {
    fn order() -> usize;
    fn zeta() -> u32;
}

impl<const M: u32> NTTFriendly for ConstantModulo<{ M }> {
    fn order() -> usize {
        Self::ORDER
    }
    fn zeta() -> u32 {
        Self::ZETA
    }
}

pub struct ModInt<T>(u32, PhantomData<fn() -> T>);

impl<T> Clone for ModInt<T> {
    fn clone(&self) -> Self {
        Self::build(self.0)
    }
}

impl<T> Copy for ModInt<T> {}

impl<T: Modulo> Add for ModInt<T> {
    type Output = Self;
    fn add(self, rhs: Self) -> Self::Output {
        let mut v = self.0 + rhs.0;
        if v >= T::modulo() {
            v -= T::modulo();
        }
        Self::build(v)
    }
}

impl<T: Modulo> Sub for ModInt<T> {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self::Output {
        let mut v = self.0 - rhs.0;
        if self.0 < rhs.0 {
            v += T::modulo();
        }
        Self::build(v)
    }
}

impl<T: Modulo> Mul for ModInt<T> {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self::Output {
        Self::build(T::reduce(self.0 as u64 * rhs.0 as u64))
    }
}

impl<T: Modulo> Div for ModInt<T> {
    type Output = Self;
    fn div(self, rhs: Self) -> Self::Output {
        self * rhs.inv()
    }
}

impl<T: Modulo> AddAssign for ModInt<T> {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl<T: Modulo> SubAssign for ModInt<T> {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl<T: Modulo> MulAssign for ModInt<T> {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl<T: Modulo> Neg for ModInt<T> {
    type Output = Self;
    fn neg(self) -> Self::Output {
        if self.is_zero() {
            Self::zero()
        } else {
            Self::build(T::modulo() - self.0)
        }
    }
}

impl<T: Modulo> std::fmt::Display for ModInt<T> {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.get())
    }
}

impl<T: Modulo> std::fmt::Debug for ModInt<T> {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.get())
    }
}

impl<T: Modulo> std::str::FromStr for ModInt<T> {
    type Err = std::num::ParseIntError;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let val = s.parse::<u32>()?;
        Ok(ModInt::new(val))
    }
}

impl<T: Modulo> From<usize> for ModInt<T> {
    fn from(v: usize) -> Self {
        Self::new_unchecked((v % T::modulo() as usize) as u32)
    }
}

impl<T> ModInt<T> {
    fn build(v: u32) -> Self {
        ModInt(v, PhantomData)
    }
    pub fn is_zero(&self) -> bool {
        self.0 == 0
    }
}

impl<T: Modulo> ModInt<T> {
    pub fn new_unchecked(v: u32) -> Self {
        Self::build(T::build(v))
    }
    pub fn new(v: u32) -> Self {
        Self::new_unchecked(v % T::modulo())
    }
    pub fn zero() -> Self {
        Self::new_unchecked(0)
    }
    pub fn one() -> Self {
        Self::new_unchecked(1)
    }
    pub fn get(&self) -> u32 {
        T::reduce(self.0 as u64)
    }
    pub fn pow(&self, mut n: u64) -> Self {
        let mut t = Self::one();
        let mut r = *self;
        while n > 0 {
            if n & 1 == 1 {
                t *= r;
            }
            r *= r;
            n >>= 1;
        }
        t
    }
    pub fn inv(&self) -> Self {
        assert!(!self.is_zero());
        self.pow((T::modulo() - 2) as u64)
    }
    pub fn fact(n: usize) -> Self {
        (1..=n).fold(Self::one(), |s, a| s * Self::from(a))
    }
}

const PRIME: u32 = 998_244_353;

type S = ConstantModulo<PRIME>;
type M = ModInt<S>;