#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
using LL = long long;

const int MAXN = 5000 + 5;
const int MAXM = 5e5 + 5;

struct Edge{ LL u, v, w; };
struct cmp{
  bool operator() (Edge i, Edge j) const {
    return i.w > j.w;
  }
};

int n, m;
LL ans = 0;
bool vis[MAXN];
vector<Edge> e[MAXN];

LL Prim(int op){
  priority_queue<Edge, vector<Edge>, cmp> E;
  LL _ans = 0;
  for(int i = 1; i <= n; i++) vis[i] = 0;
  vis[1] = 1;
  for(Edge j : e[1]) E.push({1, j.v, j.w});
  while(!E.empty()){
    Edge i = E.top();
    E.pop();
    if(vis[i.v] != vis[i.u]) _ans += i.w;
    vis[i.v] = 1, vis[i.u] = 1;
    for(Edge j : e[i.v]){
      if(i.v != j.v && vis[j.v] == 0) E.push({i.v, j.v, j.w});
    }
  }
  for(int i = 1; i <= n; i++){
    if(vis[i] == 0) return 1e18;
  }
  return _ans;
}

void work(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++) e[i].clear();
  for(int i = 1, U, V, W; i <= m; i++){
    cin >> U >> V >> W;
    e[U].push_back({0, V, W});
  }
  cout << Prim(0) << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while(T--){
    work();
  }
  return 0;
}