小 W 刚刚在离散数学课学习了生成树的知识：一个无向图 的生成树 为边集 的一个大小为 的子集，且保证 的生成子图在 中连通。

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

给定一个 个顶点 条边（点和边都从 开始编号）的无向图 ，保证图中无重边和无自环。每一条边有一个正整数边权 ，对于一棵 的生成树 ，定义 的价值为： 所包含的边的边权的最大公约数乘以边权之和，即：

其中 为 包含的边的编号。

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

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

接下来 行，每行三个正整数 ，第 行表示一条无向边连接 号点和 号点，权值为 。

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

的数据满足：。

另有 的数据满足：。

另有 的数据满足： 均相同。

另有 的数据满足： 均为质数。

的数据满足：。