#include<bits/stdc++.h>
using namespace std;
#define y1 y114514
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define all(a) a.begin(), a.end()
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int M = 1000000007;

struct edge{
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
    bool operator < (const edge& E) const{
        return w < E.w;
    }
};
vector<edge> r_edge, g_edge, b_edge;
int T, n, m, ca;
int res[111];
int fa[111];

int find(int x) { return fa[x] == x ? x  : fa[x] = find(fa[x]); }

void solve(const vector<edge>& a, const vector<edge>& b, const vector<edge>& c){
    vector<edge> ed(a), ot_ed(c);
    for(auto v : b) ed.pb(v);

    sort(all(ed));
    for(int i = 1; i <= n; ++i) fa[i] = i;
    int cnt = 0, sum = 0;
    for(auto e : ed){
        if(find(e.u) != find(e.v)){
            fa[fa[e.u]] = fa[e.v];
            sum += e.w;
            cnt++;
        }else ot_ed.pb(e);
    }
    sort(all(ot_ed));
    if(cnt < n - 1) return;
    if(res[n - 1] == -1 || res[n - 1] > sum) res[n - 1] = sum;
    for(int i = n; i <= m; ++i){
        sum += ot_ed[i - n].w;
        if(res[i] == -1 || res[i] > sum) res[i] = sum;
    }
}

int main(){
    scanf("%d", &T);
    while(T--){
        r_edge.clear();
        g_edge.clear();
        b_edge.clear();
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; ++i){
            static int a, b, w;
            static char c;
            scanf("%d%d%d %c", &a, &b, &w, &c);
            if(c == 'R'){
                r_edge.pb(edge(a, b, w));
            }else if(c == 'G'){
                g_edge.pb(edge(a, b, w));
            }else{
                b_edge.pb(edge(a, b, w));
            }
        }

        memset(res, -1, sizeof(res));
        solve(g_edge, r_edge, b_edge);
        solve(g_edge, b_edge, r_edge);
        printf("Case #%d:\n", ++ca);
        for(int i = 1; i <= m; ++i) printf("%d\n", res[i]);
    }

    return 0;
}