#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;
    std::vector<ll> mc(n, linf);
    mc[0] = 0;
    {
        ll ret = 0;
        rep(i,1,n) {
            ll min = linf;
            for(auto [u, w]: rg[i]) {
                chmin(min, w);
            }
            ret += min;
            mc[i] = min;
        }
        chmin(ans, ret);
    }
    {
        std::vector<ll> sum(n+1, 0);
        rep(i,0,n) {
            sum[i+1] = sum[i] + mc[i];
        }
        auto [u,v,w] = rev_edge;
        ll ret = sum[v] + w;
        ll min = linf;
        std::vector<ll> dp(n, linf);
        dp[u] = 0; 
        rrep(i,v+1,u+1) {
            for(auto [nv, c]: rg[i]) {
                if(nv == v) continue;
                else if(nv < v) {
                    chmin(min, dp[i] + c + sum[i] - sum[v+1]);
                }
                else {
                    chmin(dp[nv], dp[i] + c + sum[i] - sum[nv + 1]);
                }
            }
        }
        ret += min;
        chmin(ans, ret);
    }
    std::cout << ans << '\n';
}

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