思路：把每个环的最小边去掉，加在环的其他边上，然后并查集跑一下就可以，跑的时候维护一下某位为1的点有多少个

#include    <cstdio>
#include    <vector>
#include  <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
int n, m;
vector<int> G[maxn], v1, v2;
struct Edge {int u, v, cap;bool operator < (const Edge &t) const {return cap > t.cap;}
}edge[maxn<<1];
bool cmp(int i, int j) {return edge[i].cap > edge[j].cap;
}
int fa[maxn];
int que[maxn], pre[maxn], dep[maxn];
int cnt1[maxn][32], sz[maxn];void init() {v1.clear();v2.clear();for (int i = 0; i <= n; i++) G[i].clear();for (int i = 0; i <= n; i++) fa[i] = i;
}
int query(int x) { return x == fa[x] ? x : fa[x] = query(fa[x]); }
void bfs() {pre[1] = -1;dep[1] = 0;int l = 1, r = 0;que[++r] = 1;while (l <= r) {int u = que[l++];for (int i = 0; i < G[u].size(); i++) {int id = G[u][i];if (id == pre[u]) continue;int v = (u == edge[id].u ? edge[id].v : edge[id].u);pre[v] = id;dep[v] = dep[u] + 1;que[++r] = v;}}for (int i = 0; i < v2.size(); i++) {int id = v2[i];int u = edge[id].u, v = edge[id].v, cap = edge[id].cap;while (u != v) {if (dep[u] < dep[v]) swap(u, v);id = pre[u];edge[id].cap += cap;u = (u == edge[id].u ? edge[id].v : edge[id].u);}}
}
void solve() {scanf("%d%d", &n, &m);init();for (int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cap);sort(edge+1, edge+1+m);for (int i = 1; i <= m; i++) {int u = edge[i].u, v = edge[i].v;int x = query(u), y = query(v);if (x != y) {fa[x] = y;G[u].push_back(i);G[v].push_back(i);v1.push_back(i);}else {v2.push_back(i);}}bfs();sort(v1.begin(), v1.end(), cmp);int bit = 0;for (; (1<<bit) <= n; bit++);for (int i = 1; i <= n; i++) {sz[i] = 1;for (int j = 0; j < bit; j++) {cnt1[i][j] = (i>>j) & 1;}}for (int i = 0; i <= n; i++) fa[i] = i;ull ans = 0;for (int i = 0; i < v1.size(); i++) {int id = v1[i];int u = edge[id].u, v = edge[id].v, cap = edge[id].cap;int x = query(u), y = query(v);fa[x] = y;for (int j = 0; j < bit; j++) {if ((cap>>j) & 1) {ans += (1LL * (sz[x]-cnt1[x][j])*(sz[y]-cnt1[y][j]) + cnt1[x][j]*cnt1[y][j]) * (1LL<<j);}else {ans += (1LL * (sz[x]-cnt1[x][j])*cnt1[y][j] + cnt1[x][j]*(sz[y]-cnt1[y][j])) * (1LL<<j);}cnt1[y][j] += cnt1[x][j];}ans += 1LL * sz[x] * sz[y] * ((cap>>bit)<<bit);sz[y] += sz[x];}printf("%llu\n", ans);
}
int main() {int T;scanf("%d", &T);while (T--) solve();return 0;
}