#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rep2(i, l, r) for (ll i = l; i < r; i++)

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

/* ---- */
#define all(A) A.begin(), A.end()
#define elif else if
using pii = pair<ll, ll>;

bool chmin(auto &a, const auto &b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, const auto &b) { return a < b ? a = b, 1 : 0; }

struct IOSetup {
  IOSetup() {
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
} iosetup;

template <class T>
void print(vector<T> a) {
  for (auto x : a) cerr << x << ' ';
  cerr << endl;
}

void print(auto x) { cerr << x << endl; }

template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  cerr << head << ' ';
  print(forward<Tail>(tail)...);
}

ll inf=1LL<<61;

ll calc1(int n,vector<vector<pair<int,ll>>>&edge){
  vector<vector<pair<int,ll>>>redge(n);
  rep(v,n){
    for(auto [u,w]:edge[v]){
      redge[u].push_back({v,w});
    }
  }
  ll sm=0;
  rep2(i,1,n){
    if(redge[i].size()==0){
      return inf;
    }
    ll mn=inf;
    for(auto [v,w]:redge[i])mn=min(mn,w);
    sm+=mn;
  }
  return sm;
}

ll calc2(int n,vector<vector<pair<int,ll>>>&edge,int u0,int v0,ll w0){
  if(v0==0)return inf;
  // とりあえず v0 以外の頂点について最小コストの親との間に辺を貼る
  // もしループができるなら，そのループ内の頂点の親を変えてみる
  vector<vector<pair<int,ll>>>redge(n);
  rep(v,n){
    for(auto [u,w]:edge[v]){
      redge[u].push_back({v,w});
    }
  }
  vi par(n,-1);
  ll sm=0;
  rep2(i,1,n){
    if(i==v0){
      par[i]=u0;
      sm+=w0;
      continue;
    }
    if(redge[i].size()==0){
      return inf;
    }
    ll mn=inf;
    int p=-1;
    for(auto [v,w]:redge[i]){
      if(w<mn){
        mn=w;
        p=v;
      }
    }
    sm+=mn;
    par[i]=p;
  }

  // loop かチェック
  {
    int now=u0;
    while(true){
      if(now==0)return sm;
      if(now==v0)break;
      now=par[now];
    }
  }

  vi inloop(n,0);
  vvi child(n);
  rep2(i,1,n)child[par[i]].push_back(i);
  vi todo={v0};
  inloop[v0]=1;
  while(!todo.empty()){
    int v=todo.back();
    todo.pop_back();
    for(auto u:child[v]){
      if(inloop[u]==0){
        inloop[u]=1;
        todo.push_back(u);
      }
    }
  }
  

  ll ans=inf;
  {
    int now=u0;
    while(now!=v0){
      ll prev=inf,nw=inf;
      for(auto [u,w]:redge[now]){
        if(u==par[now]){
          prev=min(prev,w);
        }
        elif(inloop[u]==0){
          nw=min(nw,w);
        }
      }
      ans=min(ans,sm-prev+nw);
      now=par[now];
    }
  }
  return ans;
}

void solve(){
  int n,m;
  cin>>n>>m;
  int u0,v0,w0;
  vector<vector<pair<int,ll>>>edge(n);
  rep(i,m){
    int u,v,w;
    cin>>u>>v>>w;
    u--;v--;
    if(u<v)edge[u].push_back({v,w});
    else{
      u0=u;
      v0=v;
      w0=w;
    }
  }
  ll ans=min(calc1(n,edge),calc2(n,edge,u0,v0,w0));
  cout<<ans<<'\n';
}

int main(){
  int T;
  cin>>T;
  rep(i,T)solve();
}