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

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

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

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

边权以十进制形式给出。

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

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