#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;
    if(!m){
        cout<<n-1<<'\n';
        return;
    }
    vector<tuple<int,int,int>>ed;
    set<pair<int,int>>st;
    map<int,int>mp;
    vi a;
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        ed.eb(u,v,w);
        a.pb(u),a.pb(v);
        if(u>1)a.pb(u-1);
        if(u<n)a.pb(u+1);
        if(v>1)a.pb(v-1);
        if(v<n)a.pb(v+1);
    }
    sort(all(a)),a.erase(unique(all(a)),a.end());
    int c=a.size();
    for(int i=0;i<c;i++)mp[a[i]]=i;
    for(auto&[u,v,w]:ed){
        u=mp[u],v=mp[v];
        st.emplace(u,v),st.emplace(v,u);
    }
    DSU d(a.size());
    int cnt=0;
    ll ans=0;
    while(cnt+1<c){
        vector<pii>mn(a.size(),make_pair(2e9,-1));
        vector<int>pre(a.size(),-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(a.size(),a.size());
        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]-a[j],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]-a[i],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]<<' '<<a[j]<<endl;
            d.merge(i,j);
            ans+=mn[i].first,cnt++;
        }
    }
    cout<<ans+n-c<<'\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;
}