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

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

const ll inf=LLONG_MAX;
const int N=5e5,M=5e5;

ll ans;

int n,m;
set<int> 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];
    inline void addd(int l,int r){
        ++dcnt;
        dl[dcnt]=l;
        dr[dcnt]=r;
    }
    inline void adde(int u,int v,ll w){
        to[++ecnt]=v;
        ne[ecnt]=hd[u];
        hd[u]=ecnt;
        ed[ecnt]=w;
    }
}g;
struct edge{
    int ecnt;
    int ne[M+5],to[M+5],fr[M+5];
    ll ed[M+5];
    inline void adde(int u,int v,ll w){
        to[++ecnt]=v;
        fr[ecnt]=u;
        ed[ecnt]=w;
    }
}edges;
map<int,int> reto;
inline void rebuild(){
    int lst=1;
    for(auto iter:spl){
        int now=iter;
        if(lst<=now-1){
            g.addd(lst,now-1);
            ans+=(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+=(n-lst);
    }
    bool pd=true;
    for(int e=1;e<=edges.ecnt;e++){
        if(edges.fr[e]==1&&edges.to[e]==n||edges.fr[e]==n&&edges.to[e]==1)pd=false;
        g.adde(reto[edges.fr[e]],reto[edges.to[e]],edges.ed[e]);
        g.adde(reto[edges.to[e]],reto[edges.fr[e]],edges.ed[e]);
    }
    if(pd){
        g.adde(1,g.dcnt,1);
        g.adde(g.dcnt,1,1);
    }
}

struct DSU{
    int fa[N+5];
    int scnt;
    inline void init(int n){
        scnt=n;
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
    }
    inline int find(int x){
        if(fa[x]!=x)fa[x]=find(fa[x]);
        return fa[x];
    }
    inline void merge(int a,int b){
        a=find(a);b=find(b);
        if(a==b)return;
        fa[a]=b;
        scnt--;
    }
    inline 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";
}

inline void init(){
    ans=0;
    cin>>n>>m;
    g.ed[0]=inf;
    spl.clear();
    // reto.clear();
    // edges.clear();
    edges.ecnt=0;
    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.adde(u,v,w);
        spl.insert(u);
        spl.insert(v);
    }
}

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

int main(){
    int t;cin>>t;
    while(t--)solve();
    return 0;
}
/*
1
5 4
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
*/