Problem Description

一个图为仙人掌当且仅当每条边在至多一个简单环内且连通。给你一个仙人掌，每条边带权，对于每个点，求出这个点到其他所有点的最短路的和。

Input

第一行一个整数$T (1\leq T \leq 7)$表示数据组数。对于每组数据格式如下。

第一行两个正整数$n, m (1\leq n\leq 2 \times 10^5, 1 \leq m \leq 4 \times 10^5)$，表示点数与边数。

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

Output

对于每组数据，令$u$点的答案为$p_u$，那么输出$\sum_{u=1}^n (p_u\oplus u)*233^u$对$10^{9}+7$的值，这里的$\oplus$为异或符号。

1
5 5
5 1 2
5 2 8
5 4 9
3 2 7
4 1 4

354181127

样例解释
实际上答案应该为$(33,39,60,45,31)$。