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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;

const ll inf=1e18;
const int N=5e5,M=5e5;

ll ans;

int n,m;
map<int,bool> spl;
vector<ppi> edges;
struct graph{
    int ecnt,dcnt;
    int hd[N+5],ne[M*2+5],to[M*2+5];
    ll ed[M*2+5];
    int dl[N+5],dr[N+5];
    void addd(int l,int r){
        ++dcnt;
        dl[dcnt]=l;
        dr[dcnt]=r;
    }
    void adde(int u,int v,ll w){
        to[++ecnt]=v;
        ne[ecnt]=hd[u];
        hd[u]=ecnt;
        ed[ecnt]=w;
    }
}g;
map<int,int> reto;
void rebuild(){
    int lst=1;
    for(auto iter:spl){
        int now=iter.first;
        if(lst<=now-1){
            g.addd(lst,now-1);
            ans+=(ll)(now-lst-1);
        }
        g.addd(now,now);
        reto[now]=g.dcnt;
        lst=now+1;
        // cout<<now<<"\n";
    }if(lst<=n){
        g.addd(lst,n);
        ans+=(ll)(n-lst);
    }
    for(auto e:edges){
        pii dts=e.first;int val=e.second;
        g.adde(reto[dts.first],reto[dts.second],val);
        g.adde(reto[dts.second],reto[dts.first],val);
    }
}

struct DSU{
    int fa[N+5];
    int scnt;
    void init(int n){
        scnt=n;
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
    }
    int find(int x){
        if(fa[x]!=x)fa[x]=find(fa[x]);
        return fa[x];
    }
    void merge(int a,int b){
        a=find(a);b=find(b);
        if(a==b)return;
        fa[a]=b;
        scnt--;
    }
    bool same(int a,int b){
        return find(a)==find(b);
    }
}dsu;
int lst[N+5],nxt[N+5];
int mge[N+5],mgt[N+5];
ll mgte[N+5];
bool spld[N+5];
void burovka(){
    n=g.dcnt;
    for(int i=1;i<=n;i++){
        lst[i]=i-1;
        nxt[i]=i+1;
    }
    dsu.init(n);
    while(dsu.scnt>1){
        lst[1]=0;nxt[n]=n+1;
        for(int i=2;i<=n;i++){
            if(dsu.same(i,i-1))lst[i]=lst[i-1];
            else lst[i]=i-1;
        }
        for(int i=n-1;i>=1;i--){
            if(dsu.same(i,i+1))nxt[i]=nxt[i+1];
            else nxt[i]=i+1;
        }
        for(int i=1;i<=n;i++){
            mge[i]=0;
            for(int j=1;j<=n;j++)spld[j]=0;
            for(int e=g.hd[i];e;e=g.ne[e]){
                int j=g.to[e];
                if(dsu.same(i,j))continue;
                spld[j]=true;
                if(g.ed[e]<g.ed[mge[i]]){
                    mge[i]=e;
                }
            }
            mgt[i]=0;mgte[i]=inf;
            int l=lst[i],r=nxt[i];
            while(l>0&&(dsu.same(i,l)||spld[l])){
                if(spld[l])l--;
                else l=lst[l];
            }
            while(r<=n&&(dsu.same(i,r)||spld[r])){
                if(spld[r])r++;
                else r=nxt[r];
            }
            if(l>0){
                mgt[i]=l;
                mgte[i]=g.dl[i]-g.dr[l];
            }if(r<=n){
                if(l<=0||g.dl[r]-g.dr[i]<mgte[i]){
                    mgt[i]=r;
                    mgte[i]=g.dl[r]-g.dr[i];
                }
            }
        }
        for(int i=1;i<=n;i++){
            int f=dsu.find(i);
            if(mge[i]!=0&&g.ed[mge[f]]>g.ed[mge[i]]){
                mge[f]=mge[i];
            }
            if(mgt[i]!=0){
                if(mgt[f]==0||mgte[i]<mgte[f]){
                    mgt[f]=mgt[i];
                    mgte[f]=mgte[i];
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(dsu.fa[i]!=i)continue;
            if(mge[i]==0||mgte[i]<g.ed[mge[i]]){
                if(dsu.same(mgt[i],i))continue;
                // cout<<"mgt"<<mgt[i]<<"-"<<i<<" pay"<<mgte[i]<<" "<<ans;
                ans+=mgte[i];
                // cout<<"->"<<ans<<"\n";
                dsu.merge(mgt[i],i);
            }else{
                if(dsu.same(g.to[mge[i]],i))continue;
                // cout<<"mge"<<g.to[mge[i]]<<"-"<<i<<" pay"<<g.ed[mge[i]]<<" "<<ans;
                ans+=g.ed[mge[i]];
                // cout<<"->"<<ans<<"\n";
                dsu.merge(g.to[mge[i]],i);
            }
        }
    }
    cout<<ans<<"\n";
}

void init(){
    ans=0;
    cin>>n>>m;
    g.ed[0]=inf;
    spl.clear();
    // reto.clear();
    edges.clear();
    for(int i=1;i<=4*m+1;i++)g.hd[i]=0;
    g.dcnt=g.ecnt=0;
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        edges.push_back({{u,v},w});
        spl[u]=spl[v]=true;
    }
}

void solve(){
    init();
    rebuild();
    burovka();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}
/*
1
5 4
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
*/