#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1010;
int cas,n,m,i,f[M],A[M],ans[M];
char s[10];
struct edge{int x,y,w,col;}a[M];
bool cmp(edge a,edge b){return a.w<b.w;}
int search(int x){
    if (f[x]!=x)f[x]=search(f[x]);
    return f[x];
}
int main(){
    scanf("%d",&cas);
    for (int Cas=1;Cas<=cas;Cas++){
        printf("Case #%d:\n",Cas);
        scanf("%d%d",&n,&m);
        for (i=1;i<=m;i++){
            scanf("%d%d%d%s",&a[i].x,&a[i].y,&a[i].w,s);
            if (s[0]=='R')a[i].col=1;
                else if (s[0]=='G')a[i].col=2;
                    else a[i].col=3;
        }
        sort(a+1,a+m+1,cmp);
        for (i=1;i<=m;i++)ans[i]=1<<29;
        for (i=1;i<=n;i++)f[i]=i;
        int tmp=0,cnt=0,num=0;
        for (i=1;i<=m;i++)
            if (a[i].col!=3){
                int x=search(a[i].x),y=search(a[i].y);
                if (x!=y){f[x]=y;tmp+=a[i].w;num++;}
                    else A[++cnt]=a[i].w;
            }else A[++cnt]=a[i].w;
        if (num==n-1)
            for (i=n-1;i<=m;i++){
                ans[i]=min(ans[i],tmp);
                tmp+=A[i-n+2];
            }
        tmp=0,cnt=0,num=0;
        for (i=1;i<=n;i++)f[i]=i;
        for (i=1;i<=m;i++)
            if (a[i].col!=1){
                int x=search(a[i].x),y=search(a[i].y);
                if (x!=y){f[x]=y;tmp+=a[i].w;num++;}
                    else A[++cnt]=a[i].w;
            }else A[++cnt]=a[i].w;
        if (num==n-1)
            for (i=n-1;i<=m;i++){
                ans[i]=min(ans[i],tmp);
                tmp+=A[i-n+2];
            }
        for (i=1;i<=m;i++)
            if (ans[i]==1<<29)puts("-1");
                else printf("%d\n",ans[i]);
    }
}