题目背景

小Y在AK曼哈顿OI，CTSC和APIO之后，开始研究数学题。

题目描述

小Y有一张N个点，M条边的无向图（可能有重边、自环），每条边都有一个权值w。

你需要计算：所有生成树的边权的最大公约数之和，具体操作见样例。

由于答案可能很大，需要对1000000007取模。

输入格式

第一行两个正整数N，M，表示点数和边数。

接下来M行，每行三个正整数u，v，w，表示一条边连接u和v，权值为w。

输出格式

输出一行一个数，表示答案对1000000007取模的值。

4 5  
1 2 12  
1 3 9  
2 4 6  
3 4 8  
1 4 4  

15

提示

样例1的解释

显然，这张图有8个不同的生成树。

用$(x,y,z)$表示x,y,z的最大公约数，则答案

$=(12,6,8)+(6,8,9)+(8,9,12)+(9,12,6)+(9,4,6)+(12,4,8)+(12,4,9)+(6,4,8)$

$=2+1+1+3+1+4+1+2$

$=15$

数据范围

对于20%的数据，$N\le 10, M\le 20$；

对于另外10%的数据，$N\le 12, M\le 24$；

对于另外20%的数据，$N\le 60, M\le 3000$，且满足$u_i+1=v_i$；

对于另外20%的数据，$N\le 40, M\le 1000, W\le 1000$；

对于另外15%的数据，$N\le 50, M\le 2000$；

对于所有100%的数据，$N\le 60, M\le 3000, W\le 1000000$；