#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int inf = 999999999;
struct edge {
    int a, b, w, t;
    bool vis;
    bool operator<(const edge &r) const {
        return w < r.w;
    }
} e[maxn];
int T, n, m, p[maxn], ans[maxn];
int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}
bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    p[x] = y;
    return true;
}
void solve(int exc) {
    for (int i = 1; i <= n; ++i) p[i] = i;
    int sum = 0, cc = n, cnt = n - 1;
    for (int i = 1; i <= m; ++i) e[i].vis = false;
    for (int i = 1; i <= m && cc > 1; ++i) {
        if (e[i].t == exc) continue;
        if (merge(e[i].a, e[i].b)) --cc, sum += e[i].w, e[i].vis = true;
    }
    if (cc > 1) return;
    ans[cnt] = min(ans[cnt], sum);
    for (int i = 1; i <= m && cnt <= m; ++i) {
        if (e[i].vis) continue;
        sum += e[i].w, ++cnt;
        ans[cnt] = min(ans[cnt], sum);
    }
}
int main() {
    scanf("%d", &T);
    for (int kase = 1; kase <= T; ++kase) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) {
            static char s[5];
            scanf("%d%d%d%s", &e[i].a, &e[i].b, &e[i].w, s);
            if (*s == 'R') e[i].t = 0;
            else if (*s == 'G') e[i].t = 1;
            else e[i].t = 2;
        }
        for (int i = 1; i <= m; ++i) ans[i] = inf;
        sort(e + 1, e + m + 1);
        solve(2);
        solve(0);
        printf("Case #%d:\n", kase);
        for (int i = 1; i <= m; ++i) {
            if (ans[i] >= inf) puts("-1");
            else printf("%d\n", ans[i]);
        }
    }
    return 0;
}