#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);
      }
    }

    int64_t baseAns = 0;
    for (int i = 1; i <= n; i++) {
      if (mins[i] == INT32_MAX) {
        baseAns = INT64_MAX;
        break;
      }

      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);
        }
      }
    }

    /**
    for (int i = 1; i <= specialA; i++)
      cout << dp[i] << " ";
    cout << endl;
    cout << mins[specialB] << endl;
    */

    if (dp[specialA] != INT64_MAX)
      cout << min(baseAns, baseAns - mins[specialB] + dp[specialA] + specialW)
           << 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
*

answer.code:80:1: error: unterminated comment
   80 | /**
      | ^
answer.code: In function ‘int main()’:
answer.code:40:17: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   40 |       for (auto [u, w] : incomingEdges[i]) {
      |                 ^
answer.code:58:17: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   58 |       for (auto [u, w] : incomingEdges[i]) {
      |                 ^