#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int N = 4004000, inf = 0x3f3f3f3f3f3f3f3f;
int T, n, m, ans;
int u[N], v[N], w[N], hsh[N], t;
void add(int x) {hsh[++t] = x;}
int fa[N], s, l[N], r[N], idu[N], idv[N];
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y, int w) {
    fa[x] = y, ans += (x != y) * w;
    return;
}
int bst[N], d[N], pre[N], suf[N];
map<pii, int> mp;
map<int, bool> chk;
void solve() {
    scanf("%lld%lld", &n, &m), t = s = ans = 0, mp.clear(), chk.clear();
    for (int i = 1; i <= m; ++i) scanf("%lld%lld%lld", u + i, v + i, w + i), mp[mkp(u[i], v[i])] = mp[mkp(v[i], u[i])] = 1, add(u[i]), add(v[i]);
    sort(hsh + 1, hsh + t + 1), t = unique(hsh + 1, hsh + t + 1) - (hsh + 1);
    for (int i = 1, lst = 0; i <= t; ++i) {
        if (lst + 1 != hsh[i]) l[++s] = lst + 1, r[s] = hsh[i] - 1;
        l[++s] = hsh[i], r[s] = hsh[i], lst = hsh[i];
    }
    if (hsh[t] != n) l[++s] = hsh[t] + 1, r[s] = n;
    for (int i = 1; i <= m; ++i) idu[i] = lower_bound(l + 1, l + s + 1, u[i]) - l, idv[i] = lower_bound(l + 1, l + s + 1, v[i]) - l, chk[idu[i]] = chk[idv[i]] = 1;
    for (int i = 1; i <= s; ++i) fa[i] = i, ans += r[i] - l[i]/*, printf("[%lld,%lld]\n", l[i], r[i])*/;
    // cout << ans << '\n';
    while(1) {
        bool flg = 1;
        for (int i = 1; i <= s; ++i) flg &= (find(i) == find(1));
        if (flg) break;
        pre[1] = 0, suf[s] = s + 1;
        for (int i = 2; i <= s; ++i) 
            if (find(i) != find(i - 1)) pre[i] = i - 1;
            else pre[i] = pre[i - 1];
        for (int i = s - 1; i >= 1; --i)
            if (find(i) != find(i + 1)) suf[i] = i + 1;
            else suf[i] = suf[i + 1];
        for (int i = 1; i <= s; ++i) d[i] = inf;
        // puts("#1\n");
        for (int i = 1; i <= s; ++i) {
            if (chk[i]) {
                int u = l[i], j = i;
                while (1) {
                    if (find(j) == find(i)) j = pre[j];
                    if (!j) break;
                    for (int o = r[j]; o >= l[j]; --o) if (!mp.count(mkp(o, u))) {
                        if (u - o < d[i]) d[i] = u - o, bst[i] = j;
                        break;
                    }
                    --j;
                    if (!j) break;
                }
                j = i;
                while (1) {
                    if (find(j) == find(i)) j = suf[j];
                    if (j == s + 1) break;
                    for (int o = l[j]; o <= r[j]; ++o) if (!mp.count(mkp(u, o))) {
                        if (o - u < d[i]) d[i] = o - u, bst[i] = j/*, printf("$$ %lld:%lld %lld %lld\n", i, j, o, u)*/;
                        break;
                    }
                    ++j;
                    if (j == s + 1) break;
                }
            }
            else {
                if (pre[i] && l[i] - r[pre[i]] < d[i]) d[i] = l[i] - r[pre[i]], bst[i] = pre[i];
                if (suf[i] != s + 1 && l[suf[i]] - r[i] < d[i]) d[i] = l[suf[i]] - r[i], bst[i] = suf[i];
            }
        }
        // puts("#2\n");
        for (int i = 1; i <= m; ++i) {
            int x = find(idu[i]), y = find(idv[i]);
            if (x != y && w[i] < d[x]) d[x] = w[i], bst[x] = y;
        }
        // puts("#3\n");
        // for (int i = 1; i <= s; ++i) printf("%lld(%lld,%lld) ", find(i), bst[i], d[i]); printf("|%lld\n", ans);
        for (int x = 1; x <= s; ++x) {
            if (d[x] != inf) merge(find(x), find(bst[x]), d[x]);
        }
        // for (int i = 1; i <= s; ++i) printf("%lld ", find(i)); puts("");
    }
    printf("%lld\n", ans);
}
signed main() {
	// freopen("2.in", "r", stdin);
    scanf("%lld", &T);
    while (T--) solve();
    return 0;
}