#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T&x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
#undef gc

const int N=100+5,M=100+5,inf=1e9;
struct Edge
{
    int x,y,w;char c;
};
bool operator <(const Edge &e1,const Edge &e2)
{
    return e1.w<e2.w;
}
Edge e[M];
int fa[N];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int n,m;
bool choose[M];
int solve(char c,int k)
{
    if(k<n-1)return inf;
    rep(i,1,n)fa[i]=i;
    rep(i,1,m)choose[i]=0;
    int ans=0,ans0=0;
    rep(i,1,m)
    if(e[i].c!=c)
    {
        int x=find(e[i].x),y=find(e[i].y);
        if(x==y)continue;
        fa[x]=y;
        ++ans0;
        ans+=e[i].w;
        choose[i]=1;
    }
    if(ans0<n-1)return inf;
    rep(i,1,m)
    if(!choose[i]&&ans0<k)
    {
        ++ans0;
        ans+=e[i].w;
    }
    if(ans0<k)return inf;
    return ans;
}

int main()
{
#ifdef kcz
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
    int tt=read();
    rep(case_id,1,tt)
    {
        printf("Case #%d:\n",case_id);
        n=read();m=read();
        rep(i,1,m)
        {
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
            cin>>e[i].c;
        }
        sort(e+1,e+m+1);
        rep(i,1,m)
        {
            int ans=min(solve('R',i),solve('B',i));
            printf("%d\n",ans==inf?-1:ans);
        }
    }
}