#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

struct edge {
  int u, v, w;

  bool operator<(const edge &o) const { return w < o.w; }
};

struct dsu {
  vector<int> par, subtree;

  dsu(int n) {
    par.resize(n + 1);
    subtree.resize(n + 1);

    for (int i = 1; i <= n; i++) {
      par[i] = i;
      subtree[i] = 1;
    }
  }

  int findParent(int x) {
    if (par[x] == x)
      return x;

    par[x] = findParent(par[x]);
    return par[x];
  }

  void unite(int x, int y) {
    if (subtree[x] <= subtree[y]) {
      par[x] = y;
      subtree[y] += subtree[x];
    } else {
      par[y] = x;
      subtree[x] += subtree[y];
    }
  }
};

int64_t getMST(const vector<vector<pair<int, int>>> &g, int target) {
  int64_t res = 0;
  set<edge> currentEdges;

  for (int i = 0; i < g[1].size(); i++) {
    currentEdges.insert({1, g[1][i].first, g[1][i].second});
  }

  vector<bool> used(g.size(), false);
  used[1] = true;
  target--;

  while (!currentEdges.empty()) {
    auto e = *currentEdges.begin();
    currentEdges.erase(currentEdges.begin());
    if (!used[e.v]) {
      used[e.v] = true;
      target--;
      res += e.w;
      for (int i = 0; i < g[e.v].size(); i++) {
        currentEdges.insert({e.v, g[e.v][i].first, g[e.v][i].second});
      }
    }
  }

  if (target != 0)
    return INT64_MAX;

  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;

  while (t--) {
    int n, m;
    cin >> n >> m;

    int specialA, specialB, specialW;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
      int a, b, w;
      cin >> a >> b >> w;

      if (a < b)
        g[a].push_back({b, w});
      else {
        specialA = a;
        specialB = b;
        specialW = w;
      }
    }

    int64_t ans = getMST(g, n);

    if (specialB == 1) {
      cout << ans << endl;
      continue;
    }

    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < g[i].size(); j++) {
        if (g[i][j].first == specialA)
          g[i][j].first = specialB;
      }
    }

    for (int j = 0; j < g[specialA].size(); j++) {
      g[specialB].push_back(g[specialA][j]);
    }

    ans = min(ans, getMST(g, n - 1) + specialW);

    cout << ans << endl;
  }
}