#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<class T>
bool chmin(T &a, T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template<class T>
bool chmax(T &a, T b) {
    if(a >= b) return false;
    a = b;
    return true;
}

using pil = std::pair<int,ll>;
const ll linf = 1e17;

void solve(){
    int n,m;
    std::cin >> n >> m;
    std::vector rg(n, std::vector<pil>());
    std::tuple<int,int,ll> rev_edge;
    rep(i,0,m) {
        int u,v;
        ll w;
        std::cin >> u >> v >> w;
        u--; v--;
        if(u < v) rg[v].emplace_back(u, w);
        else rev_edge = {u, v, w};
    }
    rep(i,0,n) {
        std::sort(all(rg[i]));
    }
    ll ans = linf;
    {
        ll ret = 0;
        rep(i,1,n) {
            ll min = linf;
            for(auto [u, w]: rg[i]) {
                chmin(min, w);
            }
            ret += min;
        }
        chmin(ans, ret);
    }
    {
        std::vector dp(n, std::vector<ll>(2, linf));
        auto [u, v, w] = rev_edge;
        dp[0][0] = w;
        rep(i,1,n) {
            if(i == v) dp[i] = dp[i-1];
            else if(i < v) {
                ll min = linf;
                for(auto [nv, c]: rg[i]) {
                    chmin(min, c);
                }
                chmin(dp[i][0], dp[i-1][0] + min);
            }
            else {
                for(auto [nv, c]: rg[i]) {
                    if(nv < v) {
                        chmin(dp[i][1], dp[i - 1][0] + c);
                    }
                    chmin(dp[i][0], dp[i-1][0] + c);
                    chmin(dp[i][1], dp[i-1][1] + c);
                }
            }
        }
        chmin(ans, dp[n-1][1]);
    }
    std::cout << ans << '\n';
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int t; std::cin >> t;
    while (t--){
        solve();
    }
}