#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;
typedef pair<ll,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}

const int maxn=4e5+10;

int p[maxn];
struct Vert{
    bool spec;
    int L,R;
    unordered_map<int,int> e;
};
vector<Vert>v;

int root(int x){
    if(p[x]==x)return x;
    return p[x]=root(p[x]);
}

int n,m;

void reset_structures(){
    v.clear();
}

void go(){


    scanf("%d %d",&n,&m);
    reset_structures();
    vector<pair<pii,int>>e;
    vector<int>pom;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        e.pb({{u,v},w});
        pom.pb(u);
        pom.pb(v);
    }
    pom.pb(0);
    pom.pb(n+1);
    sort(pom.begin(),pom.end());
    pom.resize(unique(pom.begin(),pom.end())-pom.begin() );

    for(int i=1;i<pom.size();i++){
        if(pom[i]-pom[i-1]>1){
            v.pb({ false,pom[i-1]+1,pom[i]-1,{} });
        }
        if(i!=pom.size()-1){
            v.pb({ true,pom[i],pom[i],{} });
        }
    }

    unordered_map<int,int>mapping;
    for(int i=0;i<v.size();i++){
        if(v[i].spec)mapping[v[i].L]=i;
        ///printf("%d %d %d AADSAFSA\n",v[i].spec,v[i].L,v[i].R);
    }

    for(int i=0;i<e.size();i++){
        int u,vv,w;
        u=mapping[e[i].ff.ff];
        vv=mapping[e[i].ff.ss];
        w=e[i].ss;
        v[u].e[vv]=w;
        v[vv].e[u]=w;
    }

    ll rez=0;
    for(int i=0;i<v.size();i++)rez+=(ll)v[i].R-v[i].L;

    n=v.size();
    int cc=n;
    for(int i=0;i<n;i++)p[i]=i;
    vector<pair<int,pii>>cand(n);
    vector<int>prv(n),nxt(n);
    while(cc>1){

        prv[0]=-1;
        for(int i=1;i<n;i++)prv[i]=( root(i)==root(i-1)?prv[i-1]:i-1);
        nxt[n-1]=n;
        for(int i=n-2;i>=0;i--)nxt[i]=( root(i)==root(i+1)?nxt[i+1]:i+1);
        for(int i=0;i<n;i++)cand[i]={2e9,{-1,-1}};

        for(int i=0;i<n;i++){

            int r=root(i);

            if(v[i].spec){

                for(unordered_map<int,int>::iterator it=v[i].e.begin();it!=v[i].e.end();it++){
                    if(root(it->ff)==r)continue;
                    cand[r]=min(cand[r], {it->ss, {i,it->ff} } );
                }

                int curr=i;
                while(curr!=-1){

                    if(root(curr)==r){
                        curr=prv[curr];
                        continue;
                    }

                    if(v[i].e.find(curr)!=v[i].e.end()){
                        curr--;
                        continue;
                    }


                    break;
                }
                ///printf("%d CURR LEFT\n",curr);
                if(curr!=-1)cand[r]=min(cand[r], { v[i].L-v[curr].R , {i,curr} } );

                curr=i;
                while(curr!=n){

                    if(root(curr)==r){
                        curr=nxt[curr];
                        continue;
                    }

                    if(v[i].e.find(curr)!=v[i].e.end()){
                        curr++;
                        continue;
                    }

                    ///if(i==0)printf("%d %d | AA\n",i,curr);

                    break;
                }
               /// printf("%d CURRR\n",curr);
                if(curr!=n)cand[r]=min(cand[r], { v[curr].L-v[i].R , {i,curr} } );

            }
            else{

                int pom=prv[i];
                if(pom!=-1)cand[r]=min(cand[r],{ v[i].L-v[pom].R, {i,pom} });

                pom=nxt[i];
                if(pom!=n)cand[r]=min(cand[r],{ v[pom].L-v[i].R, {i,pom} });

            }

        }

        for(int i=0;i<n;i++){
            if(cand[i].ss.ss==-1)continue;
            int u=cand[i].ss.ff;
            int v=cand[i].ss.ss;
            if(root(u)==root(v))continue;
            ///printf("%d %d %d AAA\n",u,v,cand[i].ff);
            p[u]=v;
            cc--;
            rez+=cand[i].ff;
        }
        ///printf(" IZASO\n");

    }

    printf("%lld\n",rez);

}

int main(){


    ///freopen("test.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){


        go();

    }


    return 0;
}