#include<iostream>
#include<cstdio>
#include<vector>
#include<tuple>
#include<map>
#include<algorithm>
using namespace std;
const int M=400005;
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;
}