给定一张 n n n 个点 m m m 条边的带权无向图 G G G，对于 G G G 的每一棵生成树，我们定义这棵生成树的权值为：它所包含的所有边的边权按三进制不进位加法相加所得的数。
现在请你求出图 G G G 中所有的生成树的权值和（将生成树的权值由三进制转为十进制，做正常的十进制进位加法）。输出答案对 109+7 10 ^ 9 + 7 109+7 取模后的值即可。
第一行两个整数 n,m n, m n,m 表示点数与边数。点从 1∼n 1 \sim n 1∼n 编号。
接下来 m m m 行每行三个整数 a,b,c a, b, c a,b,c 表示一条连接 (a,b) (a, b) (a,b) 的边权为 c 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 \% 30% 的数据（共六个点）：n=5,6,7,8,9,10 n = 5, 6, 7, 8, 9, 10 n=5,6,7,8,9,1050% 50 \% 50% 的数据：n≤30 n \le 30 n≤3070% 70 \% 70% 的数据：n≤40 n \le 40 n≤40100% 100 \% 100% 的数据：n≤100,m≤n(n−1)2,0≤c≤104 n \le 100, m \le \frac{n(n-1)}{2}, 0 \leq c \leq 10 ^ 4 n≤100,m≤2n(n−1),0≤c≤104，保证无重边无自环。