#6271. 「长乐集训 2017 Day10」生成树求和 加强版

内存限制:512 MiB 时间限制:2000 ms 输入文件: sum.in 输出文件: sum.out
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

给定一张 n n 个点 m m 条边的带权无向图 G G ,对于 G G 的每一棵生成树,我们定义这棵生成树的权值为:它所包含的所有边的边权按三进制不进位加法相加所得的数。

现在请你求出图 G G 中所有的生成树的权值和(将生成树的权值由三进制转为十进制,做正常的十进制进位加法)。输出答案对 109+7 10 ^ 9 + 7 取模后的值即可。

输入格式

第一行两个整数 n,m n, m 表示点数与边数。点从 1n 1 \sim n 编号。

接下来 m m 行每行三个整数 a,b,c a, b, c 表示一条连接 (a,b) (a, b) 的边权为 c c 的无向边。

边权以十进制形式给出。

输出格式

仅一行一个整数表示答案。

样例

样例输入

5 7
3 2 7400
4 1 1618
4 2 9110
4 3 4264
5 1 537
5 2 4240
5 3 655

样例输出

262221

数据范围与提示

30% 30 \% 的数据(共六个点):n=5,6,7,8,9,10 n = 5, 6, 7, 8, 9, 10
50% 50 \% 的数据:n30 n \le 30
70% 70 \% 的数据:n40 n \le 40
100% 100 \% 的数据:n100,mn(n1)2,0c104 n \le 100, m \le \frac{n(n-1)}{2}, 0 \leq c \leq 10 ^ 4 ,保证无重边无自环。