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

#define pb push_back

const int N = 1e5 + 100;
const int INF = 0x3f3f3f3f;
struct Edge{
    int u, v, w;
    char c;
    Edge() {}
    Edge(int a, int b, int c, char d):u(a), v(b), w(c), c(d) {}
};
vector<Edge> edges;
int p[N], vis[N], ans[N];
int cmp(Edge a, Edge b){
    return a.w < b.w;
}
int find(int x){
    return x == p[x] ? x : p[x] = find(p[x]);
}
int solve(int n, int m, char c1, char c2){
    int sum = 0, cnt = 0;
    for (int i = 1; i <= n; i ++) p[i] = i;
    for (int i = 0; i < m; i ++) vis[i] = 0;
    for (int i = 0; i < m; i ++){
        if (edges[i].c != c1 && edges[i].c != c2) continue;
        int x = find(edges[i].u), y = find(edges[i].v);
        if (x == y) continue;
        p[y] = x;
        sum += edges[i].w;
        cnt ++;
        vis[i] = 1;
    }
    if (cnt < n - 1) return 0;
    ans[cnt] = min(ans[cnt], sum);
    int cur = 0;
    for (int i = n; i <= m; i ++){
        while (vis[cur] && cur < m) cur ++;
        sum += edges[cur].w;
        vis[cur] = 1;
        ans[i] = min(ans[i], sum);
    }
    //for (int i = 1; i <= m; i ++) printf("%d\n", ans[i]);cout << endl;
    return 0;
}
int main(){
    int T, ca = 0;
    cin >> T;
    while (T --){
        int n, m;
        scanf("%d%d", &n, &m);
        edges.clear();
        for (int i = 1; i <= m; i ++){
            int u, v, w;
            char c;
            scanf("%d %d %d %c", &u, &v, &w, &c);
            edges.pb(Edge(u, v, w, c));
            //printf("%c\n", c);
        }
        for (int i = 1; i <= m; i ++) ans[i] = INF;
        sort(edges.begin(), edges.end(), cmp);
        solve(n, m, 'R', 'G');
        solve(n, m, 'B', 'G');
        printf("Case #%d:\n", ++ ca);
        for (int i = 1; i <= m; i ++) printf("%d\n", ans[i] == INF ? -1 : ans[i]);
    }
}