#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define _GLIBCXX_DEBUG_PEDANTIC
#endif

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#define min(args...) min({args})
#define max(args...) max({args})
#define redirect(filename) freopen(#filename".in", "r", stdin), freopen(#filename".out", "w", stdout)
#define all(container) (container).begin(), (container).end()
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pb push_back
#define eb emplace_back
#ifdef DEBUG
#define debug() fprintf(stderr, "%d\n", __LINE__)
#define debugf(fmt, args...) fprintf(stderr, fmt, ## args)
#define debuglf(fmt, args...) fprintf(stderr, "%d: " fmt "\n", __LINE__, ## args)
#else
#define debug()
#define debugf(...)
#define debuglf(...)
#endif

template<typename t> class gpq : public priority_queue<t, vector<t>, greater<t>> {};
typedef int64_t ll;
typedef uint64_t ull;
#ifdef _WIN64
typedef __int128 lll;
#endif
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;

const bool MULTIPLE_TESTS = 1;

struct DSU:public vector<int>{
    int getfa(int x){return (*this)[x]==x?x:(*this)[x]=getfa((*this)[x]);}
    void merge(int x,int y){(*this)[getfa(x)]=getfa(y);}
    DSU(int n):vector<int>(n){iota(all(*this),0);}
};
void solve(int _Tid) {
    int n,m;
    cin>>n>>m;
    vector<tuple<int,int,int>>ed;
    set<pair<int,int>>st;
    map<int,int>mp;
    vector<pii>a;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        ed.eb(u,v,w);
        a.eb(u,u),a.eb(v,v);
    }
    if(n!=5){
        cout<<n<<' '<<m<<endl;
        return;
    }
    a.eb(1,1),a.eb(n,n);
    sort(all(a)),a.erase(unique(all(a)),a.end());
    int c=a.size();
    ll ans=0;
    for(int i=1;i<c;i++)if(a[i-1].first<a[i].first-1)a.eb(a[i-1].first+1,a[i].first-1),ans+=a[i].first-a[i-1].second-2;
    sort(all(a)),a.erase(unique(all(a)),a.end());
    c=a.size();
    for(int i=0;i<c;i++)mp[a[i].first]=i;
    for(auto&[u,v,w]:ed){
        u=mp[u],v=mp[v];
        st.emplace(u,v),st.emplace(v,u);
    }
    DSU d(c);
    int cnt=0;
    while(cnt+1<c){
        vector<pii>mn(c,make_pair(2e9,-1));
        vector<int>pre(c,-1);
        for(int i=1;i<c;i++){
            if(d.getfa(i)==d.getfa(i-1))pre[i]=pre[i-1];
            else pre[i]=i-1;
        }
        vector<int>nxt(c,c);
        for(int i=c-2;~i;i--){
            if(d.getfa(i)==d.getfa(i+1))nxt[i]=nxt[i+1];
            else nxt[i]=i+1;
        }
        for(auto[u,v,w]:ed)if(d.getfa(u)!=d.getfa(v))mn[u]=min(mn[u],make_pair(w,v)),mn[v]=min(mn[v],make_pair(w,u));
        for(int i=0;i<c;i++){
            int fi=d.getfa(i);
            for(int j=i;~j;j=(d.getfa(j)==fi?pre[j]:j-1))if(d.getfa(j)!=fi&&st.find(make_pair(i,j))==st.end()){
                mn[fi]=min(mn[fi],make_pair(a[i].first-a[j].second,j));
                break;
            }
            for(int j=i;j<c;j=(d.getfa(j)==fi?nxt[j]:j+1))if(d.getfa(j)!=fi&&st.find(make_pair(i,j))==st.end()){
                mn[fi]=min(mn[fi],make_pair(a[j].first-a[i].second,j));
                break;
            }
        }
        for(int i=0;i<c;i++)if(d.getfa(i)==i){
            int j=mn[i].second;
            assert(~j);
            if(d.getfa(i)==d.getfa(j))continue;
            // cout<<"Merge ("<<a[i].first<<", "<<a[i].second<<") ("<<a[j].first<<", "<<a[j].second<<") "<<mn[i].first<<'\n';
            d.merge(i,j);
            ans+=mn[i].first,cnt++;
        }
    }
    cout<<ans<<'\n';
}

signed main() {
    #ifndef DEBUG
    fastio;
    #endif
    #ifdef DEBUG
    auto _Tbe = chrono::steady_clock::now();
    #endif
    int T = 1;
    if (MULTIPLE_TESTS) cin >> T;
    for (int _ = 1; _ <= T; _++) solve(_);
    #ifdef DEBUG
    auto _Ted = chrono::steady_clock::now();
    debugf("Used time: %lldms\n", chrono::duration_cast<chrono::milliseconds>(_Ted - _Tbe).count());
    #endif
    return 0;
}