Sum of Spanning Tree Values

Given an undirected graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges (vertices and edges are numbered from 1). Each edge \(e_i\) has a positive weight \(w_i\). A spanning tree \(T\) of \(G\) is a subset of \(E\) with exactly \(n-1\) edges such that the induced subgraph is connected.

The value of a spanning tree \(T\) is defined as: \[ val(T)=\left(\sum_{i=1}^{n-1} w_{e_i}\right)\times \gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}}), \] where \(e_1,e_2,\dots,e_{n-1}\) are the edges in \(T\).

Your task is to compute the sum of \(val(T)\) over all spanning trees \(T\) of \(G\) and output the result modulo \(998244353\). It is guaranteed that the graph has no multiple edges and no self-loops.

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the number of vertices and edges.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), indicating that there is an edge between vertices \(u\) and \(v\) with weight \(w\).

Note: Vertices are numbered from 1 and the graph has no self-loops or multiple edges.

outputFormat

Output a single integer: the sum of the values of all spanning trees of \(G\) modulo \(998244353\).

sample

3 3
1 2 2
2 3 3
1 3 4

24