#include <cstdio>
#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;


const int N = 1e2 + 50;

typedef pair<int, int> pii;
vector<pair<int, pii> >es[2];
multiset<int> st[2];

int cas = 0;
int fa[N];
int getf(int x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); }
int main() {
    int T;
    cin >> T;
    while(T --) {
        printf("Case #%d:\n", ++ cas);
        st[0].clear();
        st[1].clear();
        es[0].clear();
        es[1].clear();

        int n, m;
        scanf("%d %d", &n, &m);

        for(int i = 1; i <= m; i ++) {
            int u, v, w;
            char c;
            scanf("%d %d %d %c", &u, &v, &w, &c);
            st[0].insert(w);
            st[1].insert(w);
            if(c == 'G' || c == 'R') {
                es[0].push_back(pair<int, pii>(w, pii(v, u)));
            }
            if(c == 'G' || c == 'B') {
                es[1].push_back(pair<int, pii>(w, pii(v, u)));
            }
        }

        sort(es[0].begin(), es[0].end());
        sort(es[1].begin(), es[1].end());
        
        int sum[2] = {0, 0};
        for(int c = 0; c < 2; c ++) {
            for(int i = 1; i <= n; i ++) fa[i] = i;
            for(auto it : es[c]) {
                int u = it.second.first;
                int v = it.second.second;
                if(getf(u) == getf(v)) continue;

                sum[c] += it.first;
                fa[getf(u)] = getf(v);
                st[c].erase(st[c].find(it.first));
            }
            int count = 0;
            for(int i = 1; i <= n; i ++)  count += (fa[i] == i);
            if(count > 1) sum[c] = 0x3f3f3f3f;
        }

        for(int i = 1; i <= m; i ++) {
            if(i < n - 1) puts("-1");
            else {
                  printf("%d\n", min(sum[0], sum[1]));
                   if(i == m) continue;
                
                sum[0] += *st[0].begin();
                sum[1] += *st[1].begin();
                st[0].erase(st[0].begin());
                st[1].erase(st[1].begin());
                
            }

        }
        
    }
}