#include <bits/stdc++.h>
using namespace std;
const long long llINF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
struct Edg {
  int u, v, nxt;
  long long w;
} e[N << 1], edg[N << 2], tmp[N << 1];
int n, m, dfs_clock, dfn[N], low[N], head[N], cn, cnt;
int f[N], fa[N], pos[N];
unsigned long long ans;
long long c[N][40][2];
int _find(int x) { return f[x] == x ? x : f[x] = _find(f[x]); }
void init() {
  dfs_clock = 0;
  cn = 0;
  cnt = 0;
  ans = 0;
  for (int i = 1; i <= n; i++) {
    head[i] = -1, dfn[i] = 0;
    f[i] = i;
    for (int j = 0; j <= 30; j++) {
      c[i][j][0] = ((i >> j) & 1) ^ 1;
      c[i][j][1] = (i >> j) & 1;
    }
  }
}
void addEdg(int u, int v, long long w) {
  edg[cnt].u = u, edg[cnt].v = v, edg[cnt].w = w;
  edg[cnt].nxt = head[u], head[u] = cnt++;
}
void cal_cir(int fir, int las, int q) {
  int num = 0, id = las;
  while (id != fir) {
    tmp[++num] = edg[pos[id]];
    id = fa[id];
  }
  tmp[++num] = edg[q];
  long long mn = llINF;
  for (int i = 1; i <= num; i++) {
    if (tmp[i].w < mn) {
      mn = tmp[i].w;
      id = i;
    }
  }
  for (int i = 1; i <= num; i++) {
    if (i != id) {
      e[++cn] = tmp[i];
      e[cn].w += mn;
    }
  }
}
void tarjan(int u, int f) {
  dfn[u] = low[u] = ++dfs_clock;
  fa[u] = f;
  for (int i = head[u]; ~i; i = edg[i].nxt) {
    int v = edg[i].v;
    if (v == f) continue;
    if (!dfn[v])
      pos[v] = i, tarjan(v, u), low[u] = min(low[u], low[v]);
    else
      low[u] = min(low[u], dfn[v]);
  }
  for (int i = head[u]; ~i; i = edg[i].nxt) {
    int v = edg[i].v;
    if (low[v] > dfn[u])
      e[++cn] = edg[i];
    else if (dfn[v] > dfn[u] && fa[v] != u)
      cal_cir(u, v, i);
  }
}
bool cmp(Edg a, Edg b) { return a.w > b.w; }
int main() {
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    init();
    int u, v;
    long long w;
    for (int i = 1; i <= m; i++) {
      cin >> u >> v >> w;
      addEdg(u, v, w);
      addEdg(v, u, w);
    }
    tarjan(1, -1);
    sort(e + 1, e + 1 + cn, cmp);
    for (int i = 1; i <= cn; i++) {
      int ta = _find(e[i].u), tb = _find(e[i].v);
      long long w = e[i].w;
      for (int j = 0; j <= 30; j++) {
        if (w & (1ll << j)) {
          ans += c[ta][j][0] * c[tb][j][0] * (1ll << j);
          ans += c[ta][j][1] * c[tb][j][1] * (1ll << j);
        } else {
          ans += c[ta][j][0] * c[tb][j][1] * (1ll << j);
          ans += c[ta][j][1] * c[tb][j][0] * (1ll << j);
        }
      }
      f[ta] = tb;
      for (int j = 0; j <= 30; j++) {
        c[tb][j][0] += c[ta][j][0];
        c[tb][j][1] += c[ta][j][1];
      }
    }
    cout << ans << endl;
  }
  return 0;
}
