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

typedef pair<int,int> pii;

void solv(){
    int n,m;
    cin>>n>>m;
    vector< vector<pii> >g1(n+1);

    vector<int>age, pore;
    vector<pii>lr(m+1), xy(m+1);
    vector<int>vis(n+1);

    for(int i=1; i<=m; i++){
        int l,r,x,y;
        cin>>l>>x>>r>>y;
        lr[i] = {l,r};
        xy[i] = {x,y};
        if(x==1 and y==1) age.push_back(i);
        if(x==2 and y==2){
            pore.push_back(i);
            vis[l] = vis[r] = 2;
        }
        if(x!=y){
            if(x==1){
                g1[l].emplace_back(r, i);
            }
            else{
                g1[r].emplace_back(l, i);
            }
        }
    }
    /// age, baad, majhe, pore
    vector<int>baad;
    vector<int>majhe;
    auto dfs = [&](auto &dfs, int u) -> void {
        vis[u] = 1;
        for(auto [v,idx] : g1[u]){
            if(vis[v]) {
                baad.push_back(idx);
            }
            else{
                dfs(dfs, v);
                majhe.push_back(idx);
            }
        }
    };

    for(int i=1; i<=n; i++){
        if(vis[i]==2){
            for(auto [v,idx] : g1[i]){
                if(vis[v]){
                    baad.push_back(idx);
                }
                else{
                    dfs(dfs, v);
                    majhe.push_back(idx);
                }
            }
        }
    }

    vector< vector<pii> >g(n+1);
    vector< vector<pii> >grev(n+1);

    for(int i=1; i<=n; i++){
        for(auto [v,idx] : g1[i]) {
            if(vis[i] and vis[v]) continue;
            if(!vis[i] and !vis[v]){
                g[i].emplace_back(v, idx);
                grev[v].emplace_back(i, idx);
//                cout<<"ej added "<<i<<" -> "<<v<<endl;
            }
            else if(!vis[i] and vis[v]){
                baad.push_back(idx);
            }
        }
    }

    fill(vis.begin(), vis.end(), 0);
    vector<int>order;
    vector<int>which(n+1);
    int cc = 0;

    auto dfs1 = [&](auto &dfs1, int u) -> void {
        if(vis[u]) return;
        vis[u] = true;
        for(auto [v,idx] : g[u]){
            dfs1(dfs1, v);
        }
        order.push_back(u);
    };

    auto dfs2 = [&] (auto &dfs2, int u, int id) -> void {
        if(vis[u]) return;
        vis[u] = true;
        for(auto [v,idx] : grev[u]){
            dfs2(dfs2, v, id);
        }
        which[u] = id;
    };

    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs1(dfs1, i);
        }
    }
//    cout<<"order = ";
    reverse(order.begin(), order.end());
//    for(int x : order){
//        cout<<x<<" ";
//    }
//    cout<<endl;
    fill(vis.begin(), vis.end(), 0);
    for(int u : order){
        if(vis[u]) continue;
        dfs2(dfs2, u, ++cc);
    }

//
//    for(int i=1; i<=n; i++){
//        cout<<" comp of "<<i<<" = "<<which[i]<<endl;
//    }

    vector<int>indeg(cc+1);
    for(int i=1; i<=n; i++) {
        for(auto [v,idx] : g[i]){
            indeg[ which[v] ]++;
        }
    }

    auto dfs4 = [&](auto &dfs4, int u) -> void {
        vis[u] = 1;
        for(auto [v,idx] : g[u]){
            if(vis[v]) {
                baad.push_back(idx);
            }
            else{
                dfs4(dfs4, v);
                majhe.push_back(idx);
            }
        }
    };

    fill(vis.begin(), vis.end(), 0);
    for(int i=1; i<=n; i++){
        if( indeg[ which[i] ] == 0 and !vis[i]){
            dfs4(dfs4, i);
        }
    }

    vector<int>serial = age;
    for(int x : baad) serial.push_back(x);
    for(int x : majhe) serial.push_back(x);
    for(int x : pore) serial.push_back(x);

    vector<int>arr(n+1);
    for(int idx : serial){
        arr[ lr[idx].first ] = xy[idx].first;
        arr[ lr[idx].second ] = xy[idx].second;
    }

    cout<< accumulate(arr.begin(), arr.end(), 0)<<"\n";
    for(int idx : serial) cout<<idx<<" ";
    cout<<"\n";

//    cout<<endl;
    assert(serial.size()==m);
}

/*
2
4 4
1 1 2 2
3 2 4 1
1 2 3 2
2 1 4 1
4 2
3 2 4 1
1 2 3 1
*/
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin>>tc;
    while(tc--){
        solv();
    }

    return 0;
}