[省选联考 2020 A 卷] 作业题

题目描述

小 W 刚刚在离散数学课学习了生成树的知识:一个无向图 $G=(V,E)$ 的生成树 $T$ 为边集 $E$ 的一个大小为 $|V|-1$ 的子集,且保证 $T$ 的生成子图在 $G$ 中连通。 小 W 在做今天的作业时被这样一道题目难住了: 给定一个 $n$ 个顶点 $m$ 条边(点和边都从 $1$ 开始编号)的无向图 $G$,保证图中无重边和无自环。每一条边有一个正整数边权 $w_i$,对于一棵 $G$ 的生成树 $T$,定义 $T$ 的价值为:$T$ 所包含的边的边权的最大公约数乘以边权之和,即: $$ 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}}) $$ 其中 $e_1,e_2,\dots,e_{n-1}$ 为 $T$ 包含的边的编号。 小 W 需要求出 $G$ 的所有生成树 $T$ 的价值之和,他做了很久也没做出来,请你帮帮他。由于答案可能很大,你只需要给出答案对 $998244353$ 取模后的结果。

输入输出格式

输入格式


第一行两个正整数 $n,m$,表示 $G$ 的点数和边数。 接下来 $m$ 行,每行三个正整数 $u_i,v_i,w_i$,第 $i$ 行表示一条无向边连接 $u_i$ 号点和 $v_i$ 号点,权值为 $w_i$。

输出格式


仅一行一个整数,表示答案对 $998244353$ 取模后的结果。

输入输出样例

输入样例 #1

3 3
1 2 4
2 3 6
1 3 12

输出样例 #1

192

说明

【样例解释 $1$】 $G$ 共有三棵生成树: $T_1=\{(1,2),(2,3)\}$,价值为 $10\times 2=20$。 $T_2=\{(1,2),(1,3)\}$,价值为 $16\times 4=64$。 $T_3=\{(1,3),(2,3)\}$,价值为 $18\times 6=108$。 总和为 $192$。 【数据规模】 $10\%$ 的数据满足:$m\leq 15$。 另有 $20\%$ 的数据满足:$m \leq n$。 另有 $20\%$ 的数据满足:$w_i$ 均相同。 另有 $20\%$ 的数据满足:$w_i$ 均为质数。 $100\%$ 的数据满足:$1\leq n\leq 30, 1\leq m \leq \frac {n(n-1)}{2}, 1\leq w_i \leq 152501$。