#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Edge {
    int a,b,w;
    char c[5];
    bool operator <(const Edge&tmp)const {
        return w<tmp.w;
    }
} way[105];
bool mark[2][105];
int par[105];
int find(int x) {
    if(par[x]==x)return par[x];
    return par[x]=find(par[x]);
}
int main() {
    int T,cas=0;
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&n,&m);
        for(int i=1; i<=m; i++) {
            scanf("%d %d %d %s",&way[i].a,&way[i].b,&way[i].w,way[i].c);
            mark[0][i]=mark[1][i]=0;
        }
        sort(way+1,way+1+m);
        //R G
        int res1=0,flag1=0;
        for(int i=1; i<=n; i++)par[i]=i;
        for(int i=1; i<=m; i++) {
            if(way[i].c[0]=='B')continue;
            int x=find(way[i].a),y=find(way[i].b);
            if(x==y)continue;
            mark[0][i]=1;
            par[x]=y;
            res1+=way[i].w;
        }
        for(int i=1; i<=n; i++)if(par[i]==i)flag1++;
        if(flag1>1)res1=1e9;

        //B G
        int res2=0,flag2=0;
        for(int i=1; i<=n; i++)par[i]=i;
        for(int i=1; i<=m; i++) {
            if(way[i].c[0]=='R')continue;
            int x=find(way[i].a),y=find(way[i].b);
            if(x==y)continue;
            mark[1][i]=1;
            par[x]=y;
            res2+=way[i].w;
        }
        for(int i=1; i<=n; i++)if(par[i]==i)flag2++;
        if(flag2>1)res2=1e9;

        printf("Case #%d:\n",++cas);
        for(int k=1; k<n-1; k++) {
            printf("-1\n");
        }
        int ans=min(res1,res2);
        //printf("res1=%d res2=%d\n",res1,res2);
        printf("%d\n",ans<1e9?ans:-1);
        int L1=1,L2=1;
        for(int k=n; k<=m; k++) {
            while(L1<=m&&mark[0][L1])L1++;
            if(L1<=m){
                res1+=way[L1].w;
                mark[0][L1]=1;
            }
            while(L2<=m&&mark[1][L2])L2++;
            if(L2<=m){
                res2+=way[L2].w;
                mark[1][L2]=1;
            }
            //printf("res1=%d res2=%d\n",res1,res2);
            ans=min(res1,res2);
            printf("%d\n",ans<1e9?ans:-1);
        }
    }
    return 0;
}