Description

Little W has just learned about spanning trees in a discrete mathematics class: a spanning tree $T$ of an undirected graph $G=(V,E)$ is a subset of the edge set $E$ with size $|V|-1$, and the subgraph generated by $T$ is connected in $G$.

While doing today’s homework, Little W got stuck on the following problem:

Given an undirected graph $G$ with $n$ vertices and $m$ edges (both vertices and edges are numbered starting from $1$), it is guaranteed that there are no multiple edges and no self-loops in the graph. Each edge has a positive integer weight $w_i$. For a spanning tree $T$ of $G$, define the value of $T$ as: the greatest common divisor of the weights of the edges in $T$ multiplied by the sum of these weights, that is:

$$val(T)=\left(\sum\limits_{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 indices of the edges included in $T$.

Little W needs to find the sum of the values of all spanning trees $T$ of $G$. Since the answer may be very large, you only need to output it modulo $998244353$.

Input Format

The first line contains two positive integers $n,m$, representing the number of vertices and edges of $G$.

The next $m$ lines each contain three positive integers $u_i,v_i,w_i$. The $i$-th line describes an undirected edge connecting vertex $u_i$ and vertex $v_i$, with weight $w_i$.

Output Format

Output a single integer in one line, representing the answer modulo $998244353$.

3 3
1 2 4
2 3 6
1 3 12

192

Hint

[Sample Explanation 1]

There are three spanning trees in $G$:

$T_1=\{(1,2),(2,3)\}$, with value $10\times 2=20$.

$T_2=\{(1,2),(1,3)\}$, with value $16\times 4=64$.

$T_3=\{(1,3),(2,3)\}$, with value $18\times 6=108$.

The total sum is $192$.

[Constraints]

$10\%$ of the testdata satisfies: $m\leq 15$.

Another $20\%$ of the testdata satisfies: $m \leq n$.

Another $20\%$ of the testdata satisfies: all $w_i$ are equal.

Another $20\%$ of the testdata satisfies: all $w_i$ are prime numbers.

$100\%$ of the testdata satisfies: $1\leq n\leq 30, 1\leq m \leq \frac {n(n-1)}{2}, 1\leq w_i \leq 152501$。

Translated by ChatGPT 5