#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
using namespace std;
const int N=1e3+100;
struct edge{
    int u,v,c;
    LL w;
}e[N];
int n,m,k,T,tot,t;
int u,v;
LL w;
char s[10];
bool tag[2][N];
int num[3];
LL ans[N];
LL minx[2];
int fa[N];
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
inline int Find(int i)
{
    return fa[i]==i?i:(fa[i]=Find(fa[i]));
}
inline void Union(int u,int v)
{
    fa[Find(u)]=Find(v);
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for(int kase=1;kase<=T;kase++)
    {
        cout<<"Case #"<<kase<<":"<<endl;
        cin>>n>>m;
        tot=0;
        clr(num);
        for(int i=1;i<=m;i++)
        {
            cin>>u>>v>>w>>s;
            e[++tot]=(edge){u,v,(s[0]=='R'?0:(s[0]=='B'?1:2)),w};
            num[e[i].c]++;
        }
        sort(e+1,e+m+1,cmp);
        clr(tag);
        for(int flag=0;flag<=1;flag++)
        {
            if(m-num[flag]<n-1)
            {
                minx[flag]=INF;
                continue;
            }
            else minx[flag]=0;
            for(int i=1;i<=n;i++)
                fa[i]=i;
            for(int i=1;i<=m;i++)
            {
                ans[i]=INF;
                if(e[i].c!=flag)
                {
                    if(Find(e[i].u)!=Find(e[i].v))
                    {
                        tag[flag][i]=1;
                        Union(Find(e[i].u),Find(e[i].v));
                        minx[flag]+=e[i].w;
                    }
                }
            }
            t=0;
            for(int i=1;i<=n;i++)
            {
                if(fa[i]==i) t++;
            }
            if(t>1)
                minx[flag]=INF;
        }
        if(minx[0]==INF &&minx[1]==INF)
        {
            for(int i=1;i<=m;i++)
                cout<<"-1"<<endl;
            continue;
        }
        int f=minx[0]<minx[1]?0:1;
        for(int i=1;i<n-1;i++)
            ans[i]=-1;
        ans[n-1]=minx[f];
        for(int flag=0;flag<=1;flag++)
        {
            int k=n-1;
            if(m-num[flag]<n-1)
                continue;
            for(int i=1;i<=m;i++)
                if(tag[flag][i]==0)
                {
                    ++k;
                    minx[flag]+=e[i].w;
                    ans[k]=min(ans[k],minx[flag]);
                }
        }
        for(int i=1;i<=m;i++)
            cout<<ans[i]<<endl;
    }
    return 0;
}