/*
 * 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::basic_string<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);
}

int ans[N];
int ind[N];
int tp[N];
int dis[N];
void clear(int n, int m) {
	for (int i = 1; i <= n; i++)	G[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(ind + 1, 0, n * sizeof(int));
	dfc = 0, sn = 0;

	memset(dis + 1, 0x3f, n * sizeof(int));
}

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

void bfs() {
	std::queue<int> q;
	dfc = 0;
	for (int i = 1; i <= sn; i++)
		if (ind[i] == 0)
			q.push(scc[i][0]), dis[scc[i][0]] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (const int &v : G[u]) {
			if (dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
}

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;
	}
	std::sort(qry + 1, qry + 1 + m, [&](operators a, operators b) {
			return a.type < b.type;
			});
	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();

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

	std::sort(qry + 1, qry + 1 + m, [&](operators a, operators b) {
			if (a.type == 1 && b.type == 1) {
				int t1 = (a.x == 1 ? a.l : a.r);
				int t2 = (b.x == 1 ? b.l : b.r);
				return dis[t1] < dis[t2];
			}
			return a.type < b.type;
			});
	for (int i = m; i >= 1; i--) {
		auto &[l, r, x, y, type, id] = qry[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 = 1; i <= m; i++)
		std::cout << qry[i].id << " \n"[i == m];
}

/* 无法忘却的记忆与苍蓝之梦 */
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;
}