一个图为仙人掌当且仅当每条边在至多一个简单环内且连通。

给你一个仙人掌，每条边带权，对于每个点，求出这个点到其他所有点的最短路的和。

第一行一个整数 T（1 \le T \le 7）表示数据组数。

对于每组数据格式如下：

第一行两个正整数 n, m（1 \le n \le 2 \times 10^5，1 \le m \le 4 \times 10^5），表示点数与边数。

接下来 m 行，每行三个整数 u, v, w（1 \le u \neq v \le n，1 \le w \le 10^6），保证图中没有重边。

对于每组数据，令 u 点的答案为 p_u，那么输出：

\sum_{u=1}^{n} (p_u \oplus u) \times 233^u

对 10^9 + 7 取模的值，这里的 \oplus 为异或符号。

样例解释

实际上答案应该为 (33, 39, 60, 45, 31)。