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

const int N=105;

struct node
{
    int u,v,w;
    char col;
}a[N];

int fa[N];

int find(int x)
{
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}

bool vis[N];
int ans[N],n,m;
char s[3];

void work(char col1,char col2)
{
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=0;i<m;i++) vis[i] = false;
    int sum=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        if(a[i].col!=col1 && a[i].col!=col2) continue;
        int u=a[i].u,v=a[i].v;
        if(find(u)!=find(v))
        {
            fa[find(u)] = find(v);
            sum+=a[i].w;
            cnt++;
            vis[i] = true;
        }
    }
    if(cnt!=n-1) return;
    ans[n-1] = min(ans[n-1],sum);
    int k = n-1;
    for(int i=0;i<m;i++)
    {
        if(vis[i]) continue;
        sum += a[i].w;
        k++;
        ans[k] = min(ans[k],sum);
    }
}

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d %d %d %s",&a[i].u,&a[i].v,&a[i].w,s);
            a[i].col=s[0];
        }
        sort(a,a+m,[](node a,node b){return a.w<b.w;});
        memset(ans,0x3f,sizeof(ans));
        work('R','G');
        work('G','B');
        printf("Case #%d:\n",++cas);
        for(int i=1;i<=m;i++)
        {
            if(ans[i]==0x3f3f3f3f) ans[i]=-1;
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}