#include<bits/stdc++.h>
#define rep(i,l,r) for (int i=l;i<=r;i++)
typedef long long ll;
using namespace std;
const int maxn=205;
const int inf=1e9;
struct data{int x,y,c,boo;char op;}e[maxn*2];
int f[maxn],ans[maxn];
int t,n,m,sum,cnt;
bool cmp(data a,data b){
    return a.c<b.c;
}
int find(int x){
    if (f[x]==x) return f[x];
    return f[x]=find(f[x]);
}
int main(){
    scanf("%d",&t);
    rep(ii,1,t){
        printf("Case #%d:\n",ii);
        scanf("%d%d",&n,&m);
        rep(i,1,m){
            scanf("%d%d%d %c",&e[i].x,&e[i].y,&e[i].c,&e[i].op); 
        }
        rep(i,1,m) ans[i]=inf; 
        sort(e+1,e+1+m,cmp);
        
        sum=0; cnt=0;
        rep(i,1,n) f[i]=i;
        rep(i,1,m) e[i].boo=0;
        rep(i,1,m) if (e[i].op=='R'||e[i].op=='G'){
            int x=find(e[i].x),y=find(e[i].y);    
            if (x!=y) sum+=e[i].c,f[find(x)]=find(y),cnt++,e[i].boo=1;
        }
        if (cnt==n-1){
            ans[cnt]=min(ans[cnt],sum); 
            rep(i,1,m) if (!e[i].boo) 
                sum+=e[i].c,cnt++,ans[cnt]=min(ans[cnt],sum);
        }
        
        sum=0; cnt=0;
        rep(i,1,n) f[i]=i;
        rep(i,1,m) e[i].boo=0;
        rep(i,1,m) if (e[i].op=='B'||e[i].op=='G'){
            int x=find(e[i].x),y=find(e[i].y);    
            if (x!=y) sum+=e[i].c,f[find(x)]=find(y),cnt++,e[i].boo=1;
        }
        if (cnt==n-1){
            ans[cnt]=min(ans[cnt],sum); 
            rep(i,1,m) if (!e[i].boo) 
                sum+=e[i].c,cnt++,ans[cnt]=min(ans[cnt],sum);
        }
        rep(i,1,m) if (ans[i]==inf) puts("-1");
        else printf("%d\n",ans[i]); 
    }    
    return 0;
}