UOJ Logo Universal Online Judge

UOJ

#544. 【统一省选2020】作业题

附件下载 统计

小 W 刚刚在离散数学课学习了生成树的知识:一个无向图 G=(V,E) 的生成树 T 为边集 E 的一个大小为 |V|1 的子集,且保证 T 的生成子图在 G 中连通。

小 W 在做今天的作业时被这样一道题目难住了:

给定一个 n 个顶点 m 条边(点和边都从 1 开始编号)的无向图 G,保证图中无重边和无自环。每一条边有一个正整数边权 wi,对于一棵 G 的生成树 T,定义 T 的价值为:T 所包含的边的边权的最大公约数乘以边权之和,即:

val(T)=(i=1n1wei)×gcd(we1,we2,,wen1)

其中 e1,e2,,en1T 包含的边的编号。

小 W 需要求出 G 的所有生成树 T 的价值之和,他做了很久也没做出来,请你帮帮他。由于答案可能很大,你只需要给出答案对 998244353 取模后的结果。

输入格式

第一行两个正整数 n,m,表示 G 的点数和边数。

接下来 m 行,每行三个正整数 ui,vi,wi,第 i 行表示一条无向边连接 ui 号点和 vi 号点,权值为 wi

输出格式

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

样例1

input

3 3
1 2 4
2 3 6
1 3 12

output

192

explanation

G 共有三棵生成树:

T1={(1,2),(2,3)},价值为 10×2=20

T2={(1,2),(1,3)},价值为 16×4=64

T3={(1,3),(2,3)},价值为 18×6=108

总和为 192

样例2

见附加文件中 ex_count2.inex_count2.ans

数据范围

对于前 10% 的数据满足:m15

另有 20% 的数据满足:mn

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

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

对于 100% 的数据满足:1n30,1mn(n1)2,1wi152501

时间限制: 3s

空间限制: 512MB