#3304. 「联合省选 2020 A」作业题

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

小 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_{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

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

样例 2

见附加文件中 count2.incount2.ans

数据范围与提示

10\% 的数据满足: m\le 15

另有 20\% 的数据满足: m \le n

另有 20\% 的数据满足: w_i 均相同。

另有 20\% 的数据满足: w_i 均为质数。

100\% 的数据满足: 2\le n\le 30, 1\le m \le \frac {n(n-1)}2, 1\le w_i \le 152501