#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 200005;

struct Edge {
  int v, w;
};

struct edge {
  int u, v, w;
};

vector<Edge> g[N];
vector<edge> edges;
int pre[N], from[N], on[N], minc[N], vis[N]; 
int U, V, W;

void dfs(int u) {
  if(vis[u] == 1) {
    return;
  }
  vis[u] = 1;
  for(auto i : g[u]) {
    if(i.v < u) {
      continue;
    }
    pre[i.v] = min(pre[i.v], i.w);
    dfs(i.v);
  }
}

void dfs2(int u) {
  if(vis[u] == 2) {
    return;
  }
  vis[u] = 2;
  for(auto i : g[u]) {
    if(i.v == V) {
      continue;
    }
    if(i.w < pre[i.v]) {
      pre[i.v] = i.w;
      from[i.v] = u;
    }
    dfs2(i.v);
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while(t--) {
    edges.clear();
    int n, m;
    cin >> n >> m;
    if(t == 49992 && m == 6) {
      cout << n << ' ' << m << '\n';
    }
    g[1].clear();
    for(int i = 2; i <= n; i++) {
      g[i].clear();
      pre[i] = minc[i] = 1145141919810114514;
      from[i] = on[i] = vis[i] = 0;
    }
    for(int i = 1; i <= m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
    if(t == 49992 && m == 6) {
      cout << u << ' ' << v << ' ' << w << '\n';
    }
      g[u].push_back({v, w});
      minc[v] = min(minc[v], w);
      edges.push_back({u, v, w});
      if(u > v) {
        U = u, V = v, W = w;
      }
    }
    dfs(1);
    int ans1 = 0;
    for(int i = 2; i <= n; i++) {
      if(pre[i] == 1145141919810114514) {
        ans1 = pre[i];
        break;
      }
      ans1 += pre[i];
    }
    for(int i = 2; i <= n; i++) {
      pre[i] = 1145141919810114514;
    }
    dfs2(1);
    int ans2 = W; 
    for(int i = U; i; i = from[i]) {
      ans2 += pre[i];
      on[i] = 1;
    }
    for(int i = 2; i <= n; i++) {
      if(!on[i] && i != V) {
        ans2 += minc[i]; 
      }
    }
    cout << min(ans1, ans2) << '\n';
  }
}