#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxm=100+10,inf=0x3f3f3f3f;
struct Edge{
    int x,y,z;
    bool operator <(const Edge &rhs) const{
        return z<rhs.z;
    }
}A[maxm],B[maxm],C[maxm],E1[maxm],E2[maxm];
int n,n1,n2,n3,t1,t2,m;
int ans[maxm],fa[maxm];
bool p1[maxm];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
char s[10];
void work(){
    memset(p1,0,sizeof(p1));
    sort(E1+1,E1+t1+1),sort(E2+1,E2+t2+1);
    assert(t1+t2==m);
    REP(i,1,n) fa[i]=i;
    int tmp=0,num=0;
    REP(i,1,t1){
        int x=E1[i].x,y=E1[i].y;
        if(find(x)==find(y)) continue;
        fa[find(x)]=find(y);
        ++tmp,num+=E1[i].z;
        p1[i]=1;
        if(tmp==n-1) break;
    }
    if(tmp<n-1) return;
    chkmin(ans[n-1],num);
    tmp++;
    for(int i=1,j=1;tmp<=m;++tmp){
        while(i<=t1 && p1[i]) ++i;
        if(i<=t1 && (j>t2 || E1[i].z<E2[j].z)) num+=E1[i].z,chkmin(ans[tmp],num),++i;
        else num+=E2[j].z,chkmin(ans[tmp],num),++j;
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("f.in","r",stdin);
    freopen("f.out","w",stdout);
#endif
    int T=read();
    REP(_,1,T){
        n1=n2=n3=0;
        n=read(),m=read();
        REP(i,1,m){
            int x=read(),y=read(),z=read();
            scanf("%s",s+1);
            if(s[1]=='R') A[++n1]=(Edge){x,y,z};
            else if(s[1]=='G') B[++n2]=(Edge){x,y,z};
            else C[++n3]=(Edge){x,y,z};
        }
        t1=t2=0;
        REP(i,1,n1) E1[++t1]=A[i];
        REP(i,1,n2) E1[++t1]=B[i];
        REP(i,1,n3) E2[++t2]=C[i];
        memset(ans,inf,sizeof(ans));
        work();
        t1=t2=0;
        REP(i,1,n1) E2[++t2]=A[i];
        REP(i,1,n2) E1[++t1]=B[i];
        REP(i,1,n3) E1[++t1]=C[i];
        work();
        printf("Case #%d:\n",_);
        REP(i,1,m) printf("%d\n",ans[i]==inf?-1:ans[i]);
    }
    return 0;
}