#include<bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair

using ll = long long;
using pii = pair<int,int>;

constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr int N = 5e5 + 10;

int T, n, m, a[N], deg[N], deg2[N];
int l[N], x[N], r[N], y[N];
bool done[N], vis[N];
vector<int> pre, ext;
vector<pii> V[N], G[N];
vector<int> S[N];
int low[N], dfn[N], dfs_cnt;
int scc_num, scc[N];
int st[N], top;
bool in_stk[N], has_out[N];

void dfs(int u){
  low[u] = dfn[u] = ++dfs_cnt;
  st[top++] = u;
  in_stk[u] = 1;
  for(auto [to, id] : V[u]){
    if(!dfn[to]){
      dfs(to);
      low[u] = min(low[u], low[to]);
    } else if(in_stk[to]){
      low[u] = min(low[u], dfn[to]);
    }
  }
  if(dfn[u] == low[u]){
    ++scc_num;
    while(true){
      --top;
      scc[st[top]] = scc_num;
      S[scc_num].pb(st[top]);
      in_stk[st[top]] = 0;
      if(st[top] == u)  break;
    }
  }
}

void update(int id){
  vis[id] = 1;
  ext.pb(id);
}

void dfs2(int x){
  deg2[x] = 0;
  for(auto [to, id] : V[x]){
    if(!vis[id] && scc[to] == scc[x]){
      update(id);
      if(deg2[to] != 0) dfs2(to);
    }
  }
}

void solve(int u){
  for(int x : S[u]){
    deg2[x] = 1;
  }
  for(int x : S[u]){
    if(done[x] || has_out[x]){
      dfs2(x);
      return;
    }
  }
  dfs2(S[u][0]);
}

void _main(){
  cin >> T;
  while(T--){
    pre.clear();
    ext.clear();
    cin >> n >> m;
    for(int i=1; i<=m; ++i){
      cin >> l[i] >> x[i] >> r[i] >> y[i];
      if(x[i] == 1 && y[i] == 1){
        pre.pb(i);
        vis[i] = 1;
      } else if(x[i] == 2 && y[i] == 2){
        vis[i] = 1;
        ext.pb(i);
        done[l[i]] = done[r[i]] = 1;
      } else {
        if(x[i] == 1){
          V[l[i]].pb(r[i], i);
        } else {
          V[r[i]].pb(l[i], i);
        }
      }
    }

    queue<int> Q;
    scc_num = 0;
    dfs_cnt = 0;
    for(int i=1; i<=n; ++i){
      if(!dfn[i]){
        top = 0;
        dfs(i);
      }
    }

    for(int i=1; i<=n; ++i){
      int x = scc[i];
      has_out[i] = 0;
      for(auto [to, id] : V[i]){
        if(x != scc[to]){
          ++deg[scc[to]];
          has_out[i] = 1;
          G[x].pb(scc[to], id);
        }
      }
    }

    for(int i=1; i<=scc_num; ++i){
      if(deg[i] == 0){
        Q.push(i);
      }
    }
    while(!Q.empty()){
      int x = Q.front(); Q.pop();
      solve(x);

      for(auto [to, id] : G[x]){
        update(id);
        if(--deg[to] == 0){
          Q.push(to);
        }
      }
    }

    reverse(ext.begin(), ext.end());
    pre.insert(pre.end(), ext.begin(), ext.end());
    for(int i=1; i<=n; ++i){
      a[i] = 0;
    }
    for(auto id : pre){
      a[l[id]] = x[id];
      a[r[id]] = y[id];
    }

    int sum = 0;
    for(int i=1; i<=n; ++i){
      sum += a[i];
    }
    cout << sum << '\n';
    for(int i=0; i<m; ++i){
      cout << pre[i] << " \n"[i == m - 1];
    }

    for(int i=1; i<=n; ++i){
      V[i].clear();
      G[i].clear();
      done[i] = 0;
      low[i] = dfn[i] = 0;
      in_stk[i] = 0;
      deg[i] = 0;
      S[i].clear();
    }
    for(int i=1; i<=m; ++i){
      vis[i] = 0;
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  _main();
  return 0;
}