#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int u,v,w;
    char col;
}ed[105];
int pre[2][105],num[2],ans[2],mark[2][105],pos[2];
bool operator<(edge a,edge b)
{
    return a.w<b.w;
}
int find(int i,int pos){return pre[pos][i]==i?i:pre[pos][i]=find(pre[pos][i],pos);}
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        memset(mark,0,sizeof(mark));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            pre[0][i]=pre[1][i]=i;
        pos[0]=pos[1]=ans[0]=ans[1]=0;
        num[0]=num[1]=n-1;
        for(int i=0;i<m;i++)
            scanf("%d%d%d%s",&ed[i].u,&ed[i].v,&ed[i].w,&ed[i].col);
        sort(ed,ed+m);
        for(int j=0;j<2;j++)
            for(int i=0;i<m;i++)
            {
                if(j==0&&ed[i].col=='B')continue;
                if(j==1&&ed[i].col=='R')continue;
                int t1=find(ed[i].u,j),t2=find(ed[i].v,j);
                if(t1!=t2)
                {
                    pre[j][t2]=t1;
                    num[j]--;
                    ans[j]+=ed[i].w;
                    mark[j][i]=1;
                }
            }
        printf("Case #%d:\n",cas++);
        for(int i=0;i<min(m,n-2);i++)printf("-1\n");
        if(num[0]&&num[1])printf("-1\n");
        else if(!num[0]&&!num[1])printf("%d\n",min(ans[0],ans[1]));
        else if(!num[0])printf("%d\n",ans[0]);
        else printf("%d\n",ans[1]);
        for(int i=n-1;i<m;i++)
        {
            for(int j=0;j<2;j++)
            {
                while(mark[j][pos[j]])pos[j]++;
                ans[j]+=ed[pos[j]].w;
                mark[j][pos[j]]=1;
            }
            if(num[0]&&num[1])printf("-1\n");
            else if(!num[0]&&!num[1])printf("%d\n",min(ans[0],ans[1]));
            else if(!num[0])printf("%d\n",ans[0]);
            else printf("%d\n",ans[1]);
        }
    }
}