文艺数学题

小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$；