#include <bits/stdc++.h>

using namespace std;

template <class T>
void read(T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <class T>
void write(T x) {
	if (x < 0) putchar('-'), write(-x);
	else if (x < 10) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}

const int _ = 1000005;

int L[_], R[_], V[_], disc[_], val[_];
bool fix[_];
vector<int> ops[_];
bool cmpL(int i, int j) {return L[i] > L[j];}

int mn[1 << 21], tag[1 << 21];
void build(int o, int l, int r) {
	mn[o] = tag[o] = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
}
void apply(int o, int x) {mn[o] += x; tag[o] += x;}
void down(int o) {apply(o << 1, tag[o]); apply(o << 1 | 1, tag[o]); tag[o] = 0;}
void change(int o, int l, int r, int ql, int qr, int x) {
	if (l == ql && r == qr) return apply(o, x);
	down(o);
	int mid = (l + r) >> 1;
	if (qr <= mid) change(o << 1, l, mid, ql, qr, x);
	else if (ql > mid) change(o << 1 | 1, mid + 1, r, ql, qr, x);
	else {
		change(o << 1, l, mid, ql, mid, x);
		change(o << 1 | 1, mid + 1, r, mid + 1, qr, x);
	}
	mn[o] = min(mn[o << 1], mn[o << 1 | 1]);
}
int query(int o, int l, int r, int ql, int qr) {
	if (l == ql && r == qr) return mn[o];
	down(o);
	int mid = (l + r) >> 1;
	if (qr <= mid) return query(o << 1, l, mid, ql, qr);
	else if (ql > mid) return query(o << 1 | 1, mid + 1, r, ql, qr);
	else return min(query(o << 1, l, mid, ql, mid), query(o << 1 | 1, mid + 1, r, mid + 1, qr));
}

int main() {
	int T; read(T);
	while (T--) {
		int N, M; read(N); read(M);
		for (int i = 1; i <= M; ++i) {read(L[i]); read(R[i]); read(V[i]);}
		copy(V + 1, V + M + 1, disc + 1);
		sort(disc + 1, disc + M + 1);
		int cnt = unique(disc + 1, disc + M + 1) - disc - 1;
		for (int i = 1; i <= M; ++i) {
			V[i] = lower_bound(disc + 1, disc + cnt + 1, V[i]) - disc;
			ops[V[i]].push_back(i);
		}
		set<int> st; for (int i = 1; i <= N + 1; ++i) st.insert(i);
		bool flag = true;
		fill(val + 1, val + N + 1, 1);
		fill(fix + 1, fix + N + 1, false);
		for (int i = cnt; i; --i) {
			sort(ops[i].begin(), ops[i].end(), cmpL);
			int lst = N + 1;
			for (int j : ops[i]) {
				if (lst <= R[j]) continue;
				auto it = st.lower_bound(L[j]);
				if (*it > R[j]) {flag = false; break;}
				fix[lst = *it] = true;
			}
			if (!flag) break;
			for (int j : ops[i]) {
				auto it = st.lower_bound(L[j]);
				while (*it <= R[j]) {
					val[*it] = i;
					st.erase(it++);
				}
			}
		}
		for (int i = cnt; i; --i) ops[i].clear();
		if (!flag) {write(-1); putchar('\n'); continue;}
		build(1, 1, N);
		for (int i = 1; i <= N; ++i) {if (val[i] > 1) change(1, 1, N, 1, val[i] - 1, 1);}
		long long ans = 0, sum = 0;
		for (int i = N; i; --i) {
			if (!fix[i]) ans += query(1, 1, N, val[i], N);
			if (val[i] > 1) change(1, 1, N, 1, val[i] - 1, -1);
			if (fix[i] && val[i] < N) change(1, 1, N, val[i] + 1, N, 1);
		}
		for (int i = 1; i <= N; ++i) if (fix[i]) {
			ans += query(1, 1, N, val[i], val[i]);
			if (val[i] < N) change(1, 1, N, val[i] + 1, N, -1);
		}
		write(ans); putchar('\n');
	}

	return 0;
}