//
//  na 2709.cpp
//  Competitive Programming
//
//  Created by m2 on 2024/11/19.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
typedef long long int ll;
const int maxn = 1e5 + 5, maxc = 1001;
int n, m;
int siz[maxn], nxt[maxn];
inline void init(int lim){
    for(int i = 1; i <= lim; ++i){
        siz[i] = 1;
        nxt[i] = 0;
    }
}
inline int find(int idx){
    return nxt[idx]? nxt[idx] = find(nxt[idx]): idx;
}
vector<pair<int, int> > es[maxc];
inline void solve(){
    cin >> n >> m;
    for(int i = 1; i < maxc; ++i)
        es[i].clear();
    init(n);
    {
        int a, b, c;
        for(int i = 0; i < m; ++i){
            cin >> a >> b >> c;
            es[c].push_back(make_pair(a, b));
        }
    }
    ll ans = 0;
    for(int i = 1; i < maxc; ++i)
        for(pair<int, int> e: es[i])
            if((e.first = find(e.first)) != (e.second = find(e.second))){
                ans += ll(siz[e.first]) * siz[e.second] * i;
                nxt[e.first] = e.second;
                siz[e.second] += siz[e.first];
            }
    cout << ans << endl;
}
int main(){
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}