/*
 * Copyright© 2024 Heratino & Nelofus. All rights reserved.
 * author: Heratino & Nelofus
 * Problem: 
 * Tag: 
 * Memory Limit: 
 * Time Limit: 
 * Source: 
 */

// Narcissus & どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

constexpr int N = 5e5 + 10;
struct operators {
	int l, r, x, y;
	int type;
	int id;
} qry[N];
int n, m;
int dfn[N], low[N], dfc, sn;
int number[N];
bool instk[N];
int stk[N], tt;
std::vector<int> scc[N];
std::vector<operators> edg[N];
std::basic_string<int> G[N];

void dfs(int u) {
	dfn[u] = low[u] = ++dfc;
	stk[++tt] = u;
	instk[u] = true;
	for (const int &v : G[u]) {
		if (!dfn[v]) {
			dfs(v);
			low[u] = std::min(low[u], low[v]);
		} else if (instk[v]) {
			low[u] = std::min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		sn++;
		while (stk[tt] != u) {
			instk[stk[tt]] = false;
			number[stk[tt]] = sn;
			scc[sn].push_back(stk[tt--]);
		}
		instk[stk[tt]] = false;
		number[stk[tt]] = sn;
		scc[sn].push_back(stk[tt--]);
	}
}

void tarjan() {
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			dfs(i);
}

/*
 * 答案序列
 * 缩点后出度
 * 强连通分量是否有关键点
 * 询问是否已经被加入答案序列
 * 在 bfs 中的 vis
 */
int ans[N];
int otd[N];
int has[N];
int ard[N];
int vis[N];
std::vector<std::pair<int, int>> G2[N];
void clear(int n, int m) {
	for (int i = 1; i <= n; i++)	G[i].clear(), G2[i].clear();
	for (int i = 1; i <= sn; i++)	scc[i].clear();
	memset(dfn + 1, 0, n * sizeof(int));
	memset(low + 1, 0, n * sizeof(int));
	memset(ans + 1, 0, n * sizeof(int));
	memset(otd + 1, 0, n * sizeof(int));
	memset(has + 1, 0, n * sizeof(int));
	memset(ard + 1, 0, m * sizeof(int));
	memset(vis + 1, 0, n * sizeof(int));
	dfc = 0, sn = 0;
}

inline void add(int u, int v) {G[u] += v;}
int tot;
operators qans[N];

void bfs() {
	for (int u = 1; u <= n; u++)
		for (const int &v : G[u]) {
			if (number[u] != number[v]) {
				otd[number[u]]++;
			}
		}

	std::queue<int> q;
	for (int i = 1; i <= m; i++) {
		auto &[l, r, x, y, type, id] = qry[i];
		if (x == 1 && y == 2)
			G2[l].emplace_back(r, id);
		if (x == 2 && y == 1)
			G2[r].emplace_back(l, id);
		if (x == 2 && y == 2) {
			q.push(l);
			q.push(r);
			qans[++tot] = qry[i];
			has[number[l]] = 1;
			has[number[r]] = 1;
			ard[id] = 1;
		}
	}
	for (int i = 1; i <= sn; i++)
		if (otd[i] == 0 && !has[i]) {
			q.push(scc[i][0]);
			has[i] = 1;
		}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (const auto &[v, qryid] : G2[u]) {
			if (!ard[qryid]) {
				ard[qryid] = 1, q.push(v);
				qans[++tot] = qry[qryid];
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		auto &[l, r, x, y, type, id] = qry[i];
		if (x == 1 && y == 1)
			qans[++tot] = qry[i];
	}
}

void solve() {
	std::cin >> n >> m;
	clear(n, m);
	for (int i = 1; i <= m; i++) {
		auto &[l, r, x, y, type, id] = qry[i];
		std::cin >> l >> x >> r >> y;
		if (x == 1 && y == 1)
			type = 0;
		else if (x == 2 && y == 2)
			type = 2;
		else
			type = 1;
		id = i;
	}

	for (int i = 1; i <= m; i++) {
		auto &[l, r, x, y, type, id] = qry[i];
		if (x == 1 && y == 2)
			add(r, l);
		if (x == 2 && y == 1)
			add(l, r);
	}

	tarjan();
	bfs();

	for (int i = 1; i <= m; i++) {
		auto &[l, r, x, y, type, id] = qans[i];
		if (ans[l] == 0)
			ans[l] = x;
		if (ans[r] == 0)
			ans[r] = y;
	}
	int res = 0;
	for (int i = 1; i <= n; i++)
		res += ans[i];
	std::cout << res << '\n';
	// 正序输出
	for (int i = m; i >= 1; i--)
		std::cout << qans[i].id << " \n"[i == 1];
}

/* 无法忘却的记忆与苍蓝之梦 */
int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T;
	std::cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}