#include<iostream>
#include<cstdio>
#include<vector>
#include<tuple>
#include<map>
#include<algorithm>
using namespace std;
const int M=200005;
const int INF=1061109567;
int n,m;
struct Edge
{
    int u,v,w;
}e[M];
int b[M],cnt;
int pre[M],suf[M];
pair<int,int>p[M];
int tot;
int fa[M];
int getf(int v)
{
    if(v==fa[v]) return v;
    else return fa[v]=getf(fa[v]);
}
vector<pair<int,int>>G[M];
map<pair<int,int>,bool>vis;
void solve()
{
    cin>>n>>m;
    cnt=0;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
        b[++cnt]=e[i].u,b[++cnt]=e[i].v;
    }
    if(m==0)
    {
        cout<<n-1<<"\n";
        return;
    }
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-b-1;
    b[0]=0;
    long long ans=0;
    tot=0; 
    for(int i=1;i<=cnt;i++)
    {
        if(b[i-1]+1<=b[i]-1) p[++tot]={b[i-1]+1,b[i]-1},ans+=b[i]-1-(b[i-1]+1);
        p[++tot]={b[i],b[i]};
    }
    if(b[cnt]+1<=n) p[++tot]={b[cnt]+1,n},ans+=n-(b[cnt]+1);
    vis.clear();
    for(int i=1;i<=n;i++)
        G[i].clear();
    for(int i=1;i<=m;i++)
    {
        int u=lower_bound(p+1,p+tot+1,make_pair(e[i].u,e[i].u))-p,v=lower_bound(p+1,p+tot+1,make_pair(e[i].v,e[i].v))-p,w=e[i].w;
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
        vis[{u,v}]=vis[{v,u}]=true;
    }
    for(int i=1;i<=tot;i++)
    {
        pre[i]=p[i].first-1,suf[i]=p[i].second+1;
        while(pre[i]>=1&&vis.count({i,pre[i]})) pre[i]--;
        while(suf[i]<=tot&&vis.count({i,suf[i]})) suf[i]++;
    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int t=n;t>1;)
    {
        vector<tuple<int,int,int>>edge;
        for(int u=1;u<=tot;u++)
        {
            int val=INF,to=0;
            for(auto [v,w]:G[u])
                if(getf(v)!=getf(u)&&w<=val) to=v,val=w;
            if(pre[u]>=1)
            {
                int v=pre[u],w=p[u].first-p[v].second;
                if(w<=val) to=v,val=w;
            }
            if(suf[u]<=tot)
            {
                int v=suf[u],w=p[v].first-p[u].second;
                if(w<=val) to=v,val=w;
            }
            edge.emplace_back(u,to,val);
        }
        for(auto [u,v,w]:edge)
        {
            if(u>v) swap(u,v);
            int fu=getf(u),fv=getf(v);
            if(fu==fv) continue;
            fa[fv]=fu;
            ans+=w;
            t--;
            if(getf(pre[u])==getf(u))
            {
                int t=pre[pre[u]];
                pre[u]=t;
            }
            if(getf(suf[u])==getf(u))
            {
                int t=suf[suf[u]];
                suf[u]=t;
            }
            if(getf(pre[v])==getf(v))
            {
                int t=pre[pre[v]];
                pre[v]=t;
            }
            if(getf(suf[v])==getf(v))
            {
                int t=suf[suf[v]];
                suf[v]=t;
            }
        }
    }
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}