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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const ll infl = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int MAXN = 105;


int n, m;

struct Edge{
    int u, v, w, flag;
    bool operator < (const Edge& e) const {
        return w < e.w;
    }
};
vector<Edge> G1, G2;
vector<Edge> red, green, blue;
int fa[MAXN];

int F(int x) { return -1 == fa[x] ? x : fa[x] = F(fa[x]); }
int ansk[MAXN];

int kruskal(vector<Edge>& G) {
    memset(fa, -1, sizeof(fa));
    sort(G.begin(), G.end());
    int cnt = 0, ret = 0;
    for(int i = 0; cnt < n - 1 && i < G.size(); ++i) {
        int pa = F(G[i].u), pb = F(G[i].v);
        if(pa == pb) continue;
        cnt += 1;
        G[i].flag = true;
        ret += G[i].w;
        fa[pb] = pa;
    }
    return cnt < n - 1 ? -1 : ret;
}

void solve(vector<Edge>& Gx, vector<Edge>& Gy) {
    int ret = kruskal(Gx);
    if(ret != -1) {
        vector<Edge> buf;
        ansk[n - 1] = min(ansk[n - 1], ret);
        for(int i = 0; i < Gx.size(); ++i) {
            if(Gx[i].flag) continue;
            buf.push_back(Gx[i]);
        }
        for(int i = 0; i < Gy.size(); ++i) {
            buf.push_back(Gy[i]);
        }
        assert(n - 1 + buf.size() == m);
        sort(buf.begin(), buf.end());
        for(int i = n, j = 0; i <= m; ++i, ++j) {
            ansk[i] = min(ansk[i], ret + buf[j].w);
            ret += buf[j].w;
        }
    }
}

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input.txt", "r", stdin);
#endif
    int T; scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas) {
        G1.clear(), G2.clear();
        red.clear(), green.clear(), blue.clear();
        scanf("%d %d", &n, &m);
        int u, v, w;
        char color[5];
        for(int i = 1; i <= m; ++i) {
            scanf("%d %d %d %s", &u, &v, &w, color);
            if(color[0] == 'R') {
                G1.push_back(Edge{u, v, w, false});
                red.push_back(Edge{u, v, w, false});
            } else if(color[0] == 'G') {
                green.push_back(Edge{u, v, w, false});
                G1.push_back(Edge{u, v, w, false});
                G2.push_back(Edge{u, v, w, false});
            } else {
                G2.push_back(Edge{u, v, w, false});
                blue.push_back(Edge{u, v, w, false});
            }
        }
        memset(ansk, 0x3f, sizeof(ansk));
        solve(G1, blue);
        solve(G2, red);
        printf("Case #%d:\n", cas);
        for(int i = 1; i <= m; ++i) {
            printf("%d\n", ansk[i] == inf ? -1 : ansk[i]);
        }
    }
    return 0;
}