#include<bits/stdc++.h>
using namespace std;
struct edge {
    int a,b,w,col;
    bool operator <(const edge &_)const {
        return w<_.w;
    }
} E[105];
int n,m,p[105];
bool mark[105];
int getfa(int x) {
    if(p[x]==x)return x;
    return p[x]=getfa(p[x]);
}
int Solve(int k,int r) {
    int ans=0,cnt=0;
    for(int i=1; i<=m; i++)
        mark[i]=0;
    for(int i=1; i<=n; i++)
        p[i]=i;
    for(int i=1; cnt<k&&i<=m; i++) {
        if(E[i].col==r)continue;
        int a=E[i].a,b=E[i].b,c=E[i].w;
        a=getfa(a),b=getfa(b);
        if(a!=b) {
            mark[i]=1;
            cnt++;
            ans+=c,p[a]=b;
        }
    }
    getfa(1);
    for(int i=2; i<=n; i++)
        if(getfa(i)!=p[1]) {
            ans=2e9;
            break;
        }
    if(ans==2e9)return ans;
    for(int i=1;cnt<k&&i<=m;i++){
        if(mark[i])continue;
        ans+=E[i].w;cnt++;
    }
    return ans;
}
int main() {
    int Time;
    scanf("%d",&Time);
    for(int I=1; I<=Time; I++) { // R G || B G
        scanf("%d%d",&n,&m);
        for(int i=1; i<=m; i++) {
            int a,b,c,col;
            char s[5];
            scanf("%d%d%d %s",&a,&b,&c,s);
            if(s[0]=='R')col=0;
            if(s[0]=='G')col=1;
            if(s[0]=='B')col=2;
            E[i]=(edge) {
                a,b,c,col
            };
        }
        sort(E+1,E+m+1);
        printf("Case #%d:\n",I);
        for(int k=1; k<=m; k++) {
            int res=min(Solve(k,0),Solve(k,2));
            if(res==2e9)puts("-1");
            else printf("%d\n",res);
        }
    }
    return 0;
}