小 W 刚刚在离散数学课学习了生成树的知识:一个无向图 G=(V,E) 的生成树 T 为边集 E 的一个大小为 |V|−1 的子集,且保证 T 的生成子图在 G 中连通。
小 W 在做今天的作业时被这样一道题目难住了:
给定一个 n 个顶点 m 条边(点和边都从 1 开始编号)的无向图 G,保证图中无重边和无自环。每一条边有一个正整数边权 wi,对于一棵 G 的生成树 T,定义 T 的价值为:T 所包含的边的边权的最大公约数乘以边权之和,即:
val(T)=(n−1∑i=1wei)×gcd
其中 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。
样例 2
见下发文件。
子任务
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。