#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MAXN = 1100000;

vector<pair<int, int>> to_right[MAXN];
vector<pair<int, int>> to_left[MAXN];

bool used[MAXN];
vector<int> G[MAXN];

void dfs(int v) {
    used[v] = true;
    for (int u : G[v]) {
        if (!used[u])
            dfs(u);
    }
}

int par[MAXN];

int get(int v) {
    if (par[v] == v)
        return v;
    return par[v] = get(par[v]);
}

bool merge(int v, int u) {
    v = get(v);
    u = get(u);
    if (v == u)
        return false;
    par[v] = u;
    return true;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<pair<int, int>, int>> edges(m);
    vector<int> interesting;
    vector<int> without;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        if (a > b)
            swap(a, b);
        if (a + 1 == b)
            without.emplace_back(a);
        edges[i] = make_pair(make_pair(a, b), c);
        interesting.emplace_back(a);
        interesting.emplace_back(b);
    }
    
    long long ans = 0;
    sort(without.begin(), without.end());
    int prev = 0;
    vector<pair<int, int>> segms;
    for (int v : without) {
        segms.emplace_back(prev, v);
        ans += v - prev;
        prev = v + 1;
    }
    segms.emplace_back(prev, n - 1);
    ans += n - 1 - prev;


    sort(interesting.begin(), interesting.end());
    interesting.resize(unique(interesting.begin(), interesting.end()) - interesting.begin());
    {
        vector<int> extra;
        int i = 0;
        for (auto [l, r] : segms) {
            int j = i;
            while (j < interesting.size() && interesting[j] <= r)
                ++j;
            // [i, j)
            int l1 = i;
            int l2 = l;
            while (l1 < j && interesting[l1] == l2) {
                ++l1;
                ++l2;
            }
            if (l2 <= r) {
                extra.emplace_back(l2);
            }
            int r1 = j - 1;
            int r2 = r;
            while (r1 >= i && interesting[r1] == r2) {
                --r1;
                --r2;
            }
            if (r2 >= l) {
                extra.emplace_back(r2);
            }
            i = j;
        }
        for (int x : extra)
            interesting.emplace_back(x);
        sort(interesting.begin(), interesting.end());
        interesting.resize(unique(interesting.begin(), interesting.end()) - interesting.begin());
    }
    

    // all the interesting
    map<int, int> ids;
    n = interesting.size();
    for (int i = 0; i < n; ++i)
        ids[interesting[i]] = i;
    for (auto [uv, w] : edges) {
        auto [u, v] = uv;
        int i1 = ids[u];
        int i2 = ids[v];
        to_right[i1].emplace_back(i2, w);
        to_left[i2].emplace_back(i1, w);
    }
    for (int i = 0; i < n; ++i) {
        sort(to_left[i].rbegin(), to_left[i].rend());
        sort(to_right[i].begin(), to_right[i].end());
    }
    {
        int i = 0;
        for (int l = 0; l < segms.size(); ++l) {
            int j = i;
            while (j < interesting.size() && interesting[j] <= segms[l].second) {
                ++j;
            }
            segms[l] = make_pair(i, j);
            i = j;
        }
    }
    vector<vector<int>> comps;
    vector<int> szs;
    vector<int> comp_id(n);
    for (int i = 0; i < segms.size(); ++i) {
        comps.emplace_back();
        comps.back().emplace_back(i);
        szs.emplace_back(segms[i].second - segms[i].first);
        for (int j = segms[i].first; j < segms[i].second; ++j)
            comp_id[j] = i;
    }

    {
        vector<pair<int, int>> free_edges;
        map<int, int> id;
        for (auto [uv, w] : edges) {
            auto [u, v] = uv;
            if (w == 0) {
                if (!id.count(u)) {
                    int new_id = id.size();
                    id[u] = new_id;
                }
                if (!id.count(v)) {
                    int new_id = id.size();
                    id[v] = new_id;
                }
                free_edges.emplace_back(id[v], id[u]);
                G[id[v]].emplace_back(id[u]);
                G[id[u]].emplace_back(id[v]);
            }
        }
        fill(used, used + id.size(), false);
        ans -= id.size();
        //cout << '-' << id.size() << '\n';
        for (int i = 0; i < id.size(); ++i) {
            if (!used[i]) {
                ++ans;
                //cout << '+' << 1 << '\n';
                dfs(i);
            }
        }
        for (int i = 0; i < id.size(); ++i) {
            G[i].clear();
        }

        iota(par, par + segms.size(), 0);
        for (auto [uv, w] : edges) {
            if (w != 0)
                continue;
            auto [u, v] = uv;
            u = ids[u];
            v = ids[v];
            int i = comp_id[u];
            int j = comp_id[v];
            if (merge(i, j)) {
                ++ans;
                //cout << '+' << 1 << '\n';
            }
        }
    }

    while (comps.size() > 1) {
        /*for (auto comp : comps) {
            cout << "comp: ";
            for (int id : comp) {
                cout << segms[id].first << ',' << segms[id].second << ' ';
            }
            cout << '\n';
        }*/
        vector<pair<int, pair<int, int>>> min_edges;
        vector<int> go_right(n);
        vector<int> go_left(n);
        iota(go_right.begin(), go_right.end(), 1);
        iota(go_left.begin(), go_left.end(), -1);
        for (auto comp : comps) {
            for (int segm_id : comp) {
                for (int i = segms[segm_id].first; i < segms[segm_id].second; ++i) {
                    go_right[i] = segms[segm_id].second;
                    go_left[i] = segms[segm_id].first - 1;
                }
            }

            pair<int, pair<int, int>> min_edge(1e9 + 228, make_pair(-1, -1));
            for (int segm_id : comp) {
                for (int i = segms[segm_id].first; i < segms[segm_id].second; ++i) {
                    int l = 0;
                    int j = go_right[i];
                    while (j < n) {
                        while (l < to_right[i].size() && to_right[i][l].first < j) {
                            ++l;
                        }
                        if (l == to_right[i].size() || to_right[i][l].first > j) {
                            break;
                        }
                        j = go_right[j];
                    }
                    if (j != n) {
                        min_edge = min(min_edge, make_pair(interesting[j] - interesting[i], make_pair(i, j)));
                    }
                    for (auto [u, w] : to_right[i]) {
                        if (comp_id[u] != comp_id[i])
                            min_edge = min(min_edge, make_pair(w, make_pair(i, u)));
                    }

                    l = 0;
                    j = go_left[i];
                    while (j > -1) {
                        while (l < to_left[i].size() && to_left[i][l].first > j) {
                            ++l;
                        }
                        if (l == to_left[i].size() || to_left[i][l].first < j) {
                            break;
                        }
                        j = go_left[j];
                    }
                    if (j != -1) {
                        min_edge = min(min_edge, make_pair(interesting[i] - interesting[j], make_pair(j, i)));
                    }
                    for (auto [u, w] : to_left[i]) {
                        if (comp_id[u] != comp_id[i])
                            min_edge = min(min_edge, make_pair(w, make_pair(u, i)));
                    }
                }
            }
            min_edges.emplace_back(min_edge);

            for (int segm_id : comp) {
                for (int i = segms[segm_id].first; i < segms[segm_id].second; ++i) {
                    go_right[i] = i + 1;
                    go_left[i] = i - 1;
                }
            }
        }

        vector<bool> alive_comp(comps.size(), true);
        for (auto min_edge : min_edges) {
            auto [w, uv] = min_edge;
            auto [u, v] = uv;
            //cout << u << ' ' << v << ' ' << w << '\n';
            u = comp_id[u];
            v = comp_id[v];
            if (u == v)
                continue;
            ans += w;
            if (szs[u] > szs[v]) {
                swap(u, v);
            }
            szs[v] += szs[u];
            for (int i : comps[u]) {
                comps[v].emplace_back(i);
                for (int j = segms[i].first; j < segms[i].second; ++j)
                    comp_id[j] = v;
            }
            alive_comp[u] = false;
        }
        vector<vector<int>> new_comps;
        vector<int> new_szs;
        for (int i = 0; i < comps.size(); ++i) {
            if (!alive_comp[i])
                continue;
            new_comps.emplace_back();
            new_szs.emplace_back(szs[i]);
            sort(comps[i].begin(), comps[i].end());
            for (int j : comps[i]) {
                while (!new_comps.back().empty() && segms[new_comps.back().back()].second == segms[j].first) {
                    segms[j].first = segms[new_comps.back().back()].first;
                    new_comps.back().pop_back();
                }
                new_comps.back().emplace_back(j);
            }
            for (int segm_id : new_comps.back()) {
                for (int j = segms[segm_id].first; j < segms[segm_id].second; ++j) {
                    comp_id[j] = new_comps.size() - 1;
                }
            }
        }
        swap(comps, new_comps);
        swap(szs, new_szs);
    }
    cout << ans << '\n';
    for (int i = 0; i < n; ++i) {
        to_left[i].clear();
        to_right[i].clear();
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}