#include <bits/stdc++.h>
#define LL long long
#define M 200
#define N 200
using namespace std;

inline LL read(){
    LL x = 0,f = 1; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}
    while (c <='9' && c >='0') {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}

inline void write(LL x){
    LL k = 0,lx = x;char put[40];
    if (lx ==0) putchar('0');
    if (lx < 0) putchar('-'),lx = -lx;
    while (lx)  put[++k] = (lx % 10) + '0',lx /= 10;
    while (k)   putchar( put[ k-- ] );
    putchar('\n');
}

int T,n,m;
LL ans[M];
//q1 red & green
//q2 blue & green
#define Red 1
#define Green 2
#define Blue 3

inline int Get(){
    char c = getchar();
    while (c != 'R' && c != 'G' && c != 'B') c = getchar();
    if (c == 'R') return Red;
    if (c == 'G') return Green;
    return Blue;
}

struct q{
    int u,v,w;
    int col;
    int rp;
    bool operator < (const q x) const{
        return w < x.w;
    }
}a[M];

void init(){
    n = read(),m = read();
    for (int i = 1; i <= m; ++i){
        a[i].u = read();
        a[i].v = read();
        a[i].w = read();
        a[i].col = Get();
        a[i].rp = 0;
    }
    sort(a+1,a+m+1);
}

int fa[N],num;
LL sum,kkk;

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

inline void NewAns(int i,LL f){
    if (ans[i] == -1) ans[i] = f; else ans[i] = min(ans[i],f);
}

void solve(){
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) a[i].rp = 0;
    for (int i = 1; i <= m; ++i) ans[i] = -1;
    
    num = n,kkk = 0,sum = 0;
    int x,y;
    for (int i = 1; i <= m && num > 1; ++i)
        if (a[i].col == Red || a[i].col == Green){
            x = Find(a[i].u);
            y = Find(a[i].v);
            if (x != y){
                --num;
                ++kkk;
                sum += a[i].w;
                fa[x] = y;
                a[i].rp = 1;
            }
        }
    
    if (num == 1){    
        NewAns(kkk,sum);
        for (int i = 1; i <= m; ++i){
            if (a[i].rp) continue;
            ++kkk;
            sum += a[i].w;
            NewAns(kkk,sum);
        }
    }
    
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= m; ++i) a[i].rp = 0;
    
    num = n,kkk = 0,sum = 0;
    for (int i = 1; i <= m && num > 1; ++i)
        if (a[i].col == Blue || a[i].col == Green){
            x = Find(a[i].u);
            y = Find(a[i].v);
            if (x != y){
                --num;
                ++kkk;
                sum += a[i].w;
                fa[x] = y;
                a[i].rp = 1;
            }
        }
    
    if (num == 1){    
        NewAns(kkk,sum);
        for (int i = 1; i <= m; ++i){
            if (a[i].rp) continue;
            ++kkk;
            sum += a[i].w;
            NewAns(kkk,sum);
        }
    }
}

int main(){
    T = read();
    for (int t = 1; t <= T; ++t){
        printf("Case #%d:\n",t);
        init();
        solve();
        for (int i = 1; i <= m; ++i) write(ans[i]);
    }
    return 0;
}