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

using namespace std;

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>>> incomingEdges(n + 1);
    for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;

      if (u < v)
        incomingEdges[v].push_back({u, w});
      else {
        specialA = u;
        specialB = v;
        specialW = w;
      }
    }

    vector<int> mins(n + 1, INT32_MAX);
    mins[1] = 0;
    for (int i = 1; i <= n; i++) {
      for (auto [u, w] : incomingEdges[i]) {
        mins[i] = min(mins[i], w);
      }
    }

    bool validBase = true;
    int64_t baseAns = 0;
    for (int i = 1; i <= n; i++) {
      if (mins[i] == INT32_MAX) {
        validBase = false;
        continue;
      }

      baseAns += mins[i];
    }

    vector<int64_t> dp(specialA + 1, INT64_MAX);
    dp[1] = 0;
    for (int i = 2; i <= specialA; i++) {
      for (auto [u, w] : incomingEdges[i]) {
        if (dp[u] != INT64_MAX && u != specialB) {
          dp[i] = min(dp[i], dp[u] - mins[i] + w);
        }
      }
    }

    if (dp[specialA] != INT64_MAX) {
      int64_t candidate = baseAns -
                          (mins[specialB] == INT32_MAX ? 0 : mins[specialB]) +
                          dp[specialA] + specialW;
      if (!validBase)
        cout << candidate << endl;
      else
        cout << min(baseAns, candidate) << endl;
    } else
      cout << baseAns << endl;
  }
}

/**
3
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
4 4
1 2 4
1 3 6
1 4 8
4 2 1000000
3 3
1 2 100
2 1 10
2 3 1000
*/