#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010, M = N << 1;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, m, ans;
// int h[N], e[M], ne[M], w[M], idx;
array<int, 3> edge[N];
int pre[N], sz[N];

// inline void add(int a, int b, int c) { e[++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx; }

int rt(int x) { return pre[x] == x ? x : pre[x] = rt(pre[x]); }

void solve()
{
    iota(pre, pre + N, 0), fill(sz, sz + N, 1);
    // memset(h, -1, sizeof h), idx = -1, ans = 0;
    ans = 0;

    read(n, m);
    for (int i = 1; i <= m; i ++)
        read(edge[i][0], edge[i][1], edge[i][2]);
    sort(edge + 1, edge + 1 + m, [](const array<int, 3> &a, const array<int, 3> &b) { return a[2] < b[2]; });

    for (int i = 1; i <= m; i ++)
    {
        int u = edge[i][0], v = edge[i][1], w = edge[i][2];
        int fx = rt(u), fy = rt(v);
        if (fx == fy) continue;

        ans += sz[fx] * sz[fy] * w;

        pre[fx] = fy, sz[fy] += sz[fx];
        // add(u, v, w), add(v, u, w);
    }
    cout << ans << '\n';
}

signed main()
{
    int T; read(T);
    while (T --) solve();
    return 0;
}