#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=1000005;
int n,m;
int fa[N];
pa all[N];
int U[N],V[N],W[N];
vector<pa>G[N];
pa mn[N];
unordered_map<int,int>ise[N];
inline int gf(int x)
{
    while (x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
void BellaKira()
{
    poly g;
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>U[i]>>V[i]>>W[i];
        g.push_back(U[i]);
        g.push_back(V[i]);
    }
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    int lst=0;
    int l_n=0;
    for (auto u:g)
    {
        if (u>lst+1) all[++l_n]=mp(lst+1,u-1);
        all[++l_n]=mp(u,u);
        lst=u;
    }
    if (lst!=n) 
        all[++l_n]=mp(lst+1,n);
        
    n=l_n;

    for (int i=1;i<=m;i++)
    {
        int x=lower_bound(all+1,all+n+1,mp(U[i],U[i]))-all;
        int y=lower_bound(all+1,all+n+1,mp(V[i],V[i]))-all;
        G[x].push_back(mp(y,i));
        G[y].push_back(mp(x,i));
        U[i]=x,V[i]=y;
        ise[x][y]=1;
        ise[y][x]=1;
    }


    int ans=0;
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<=n;i++) ans+=all[i].se-all[i].fi;
    // cerr<<"!!!!"<<n<<endl;
    while (1)
    {
        bool bl=1;
        for (int i=1;i<=n;i++)
            bl&=(gf(i)==gf(1));
        if (bl) break;
        for (int i=1;i<=n;i++)
            mn[i]=mp(inf,0);
        int lst=0;
        for (int i=2;i<=n;i++)
        {
            if (gf(i)!=gf(i-1)) lst=i-1;
            if (lst)
            {
                int op=lst;
                while (lst&&ise[i].count(lst)) lst--;
                // assert(lst>=0&&lst<=n);
                if (lst&&gf(i)!=gf(lst))
                {
                    pa nw=mp(all[i].fi-all[lst].se,(lst-1)*n+i);
                    mn[gf(i)]=min(mn[gf(i)],nw);
                }
                lst=op;
            }
        }
        lst=0;
        for (int i=n-1;i>=1;i--)
        {
            if (gf(i)!=gf(i+1)) lst=i+1;
            if (lst)
            {
                int op=lst;
                while (lst<=n&&ise[i].count(lst)) lst++;
                if (lst<=n&&gf(lst)!=gf(i))
                {
                    pa nw=mp(-all[i].se+all[lst].fi,(i-1)*n+lst);
                    mn[gf(i)]=min(mn[gf(i)],nw);
                }
                lst=op;
            }
        }
        for (int i=1;i<=n;i++)
        {
            for (auto [u,id]:G[i])
            {
                int w=W[id];
                if (gf(i)!=gf(u)) mn[gf(i)]=min(mn[gf(i)],mp(w,n*n+id));
            }
        }
        int tt=0;
        for (int i=1;i<=n;i++)
            if (gf(i)==i)
            {
                ++tt;
                int id=mn[i].se;
                int x,y;
                if (id<=n*n) x=(id-1)/n+1,y=(id-1)%n+1;
                else x=U[id-n*n],y=V[id-n*n];
                // cout<<x<<","<<y<<" "<<id<<endl;
                // assert(x>=1&&x<=n);
                // assert(y>=1&&y<=n);
                if (gf(x)!=gf(y))
                {
                    // cout<<x<<","<<y<<" "<<mn[i].fi<<" "<<mn[i].se<<endl;
                    ans+=mn[i].fi;
                    fa[gf(x)]=gf(y);
                }
            }
        // cerr<<tt<<endl;
        // cout<<"-----"<<endl;
    }
    cout<<ans<<'\n';
    for (int i=1;i<=n;i++) vector<pa>().swap(G[i]),unordered_map<int,int>().swap(ise[i]);
}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    cin>>T;
    while (T--)
    {
        BellaKira();
    }
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/