#include <bits/stdc++.h>
#define umap unordered_map

using namespace std;

const int N = 3e5 + 5;

long long ans = 0;
int loops = 0;

struct DSU{
    vector <int> par;
    int numEdge = 0;

    DSU(int n){
        par.resize(n + 3, 0);
        for (int i = 0; i <= n; ++ i) par[i] = i;
    }

    int find(int u){
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool check(int u, int v){
        return find(u) == find(v);
    }

    void joint(int u, int v, int w){
        if (check(u, v)) return;
        //if (!loops) cout << u << ' ' << v << ' ' << w << endl;
        u = find(u);
        v = find(v);
        par[u] = v;
        ans += w; ++ numEdge;
    }
};

int n, m;
int u[N], v[N], w[N], x[N], y[N];
umap <int, bool> used[N];

struct Range{
    int l, r;
};

void minl(auto &a, auto b) {a = min(a, b);}

void solve(){
    ans = 0; cin >> n >> m;
    vector <int> Point;
    for (int i = 1; i <= m; ++ i) {
        cin >> u[i] >> v[i] >> w[i];
        Point.push_back(u[i]);
        Point.push_back(v[i]);
    }
    sort(Point.begin(), Point.end());
    Point.erase(unique(Point.begin(), Point.end()), Point.end());

    vector <Range> cur;
    umap <int, int> idx;
    int last = 0;
    for (int p : Point){
        if (p > last + 1){
            cur.push_back({last + 1, p - 1});
            ans += p - last - 2;
        }
        cur.push_back({p, p});
        idx[p] = cur.size() - 1;
        last = p;
    }
    if (last < n) cur.push_back({last + 1, n}), ans += n - last - 1;
    n = cur.size();
    for (int i = 0; i < n; ++ i) used[i].clear();

    for (int i = 1; i <= m; ++ i){
        x[i] = idx[u[i]];
        y[i] = idx[v[i]];
        //cout << x[i] << ' ' << y[i] << endl;
        used[x[i]][y[i]] = 1;
        used[y[i]][x[i]] = 1;
    }

    //cout << "debug  " << cur[2].r << ' ' << cur[3].l << endl;

    DSU pqh(n);
    loops = 0;
    while (pqh.numEdge < n - 1){
        vector <int> pref(n, -1), suff(n, n);
        vector <pair <int, int>> Minto(n, {2e9, -1});
        for (int i = 1; i < n; ++ i) if (pqh.check(i, i - 1)) pref[i] = pref[i - 1]; else pref[i] = i - 1;
        for (int i = n - 2; i >= 0; -- i) if (pqh.check(i, i + 1)) suff[i] = suff[i + 1]; else suff[i] = i + 1;
        for (int i = 1; i <= m; ++ i){
            int u = pqh.find(x[i]);
            int v = pqh.find(y[i]);
            if (u != v){
                minl(Minto[u], pair <int, int> (w[i], v));
                minl(Minto[v], pair <int, int> (w[i], u));
            }
        }

        //if (pqh.numEdge == 0) cout << used[1][0] << endl;
        //cout << used[1][0] << endl;

        for (int i = 0; i < n; ++ i){
            for (int nqt = i; nqt > -1;){
                if (pqh.check(nqt, i)) nqt = pref[nqt];
                else if (used[nqt][i]) -- nqt;
                else {
                    int u = pqh.find(nqt);
                    int v = pqh.find(i);
                    int cost = cur[i].l - cur[nqt].r;
                    //if (pqh.numEdge == 0 && i == 1) cout << u << ' ' << v << ' ' << cost << endl;
                    minl(Minto[u], pair <int, int> (cost, v));
                    break;
                }
            }
            for (int nqt = i; nqt < n;){
                if (pqh.check(nqt, i)) nqt = suff[nqt];
                else if (used[nqt][i]) ++ nqt;
                else {
                    int u = pqh.find(nqt);
                    int v = pqh.find(i);
                    int cost = cur[nqt].l - cur[i].r;
                    //if (pqh.numEdge == 0 && i == 1) cout << u << ' ' << v << ' ' << cost << endl;
                    minl(Minto[v], pair <int, int> (cost, u));


                    break;
                }
            }
        }

        for (int i = 0; i < n; ++ i) if (Minto[i].second > -1) pqh.joint(i, Minto[i].second, Minto[i].first);
        ++ loops;
    }

    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) solve();

    return 0;
}