#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=110;
int T,n,m,ans[maxn];
int p[maxn];
bool vis[3][maxn];
struct node
{
    int u;
    int v;
    int c;
    int col;
}e[maxn];
bool cmp(node a,node b)
{
    return a.c<b.c;
}
int cha(int x)
{
    if(p[x]==-1)
        return x;
    return p[x]=cha(p[x]);
}
int find(int id,int col1,int col2)
{
    int sum=0;
    int cnt=0;
    memset(p,-1,sizeof(p));
    for(int i=1;i<=m;i++)
    {
        if(e[i].col!=col1&&e[i].col!=col2)
            continue;
        int x=cha(e[i].u);
        int y=cha(e[i].v);
        if(x!=y)
        {
            p[x]=y;
            sum+=e[i].c;
            cnt++;
            vis[id][i]=1;
            if(cnt==n-1)
                break;
        }
    }
    if(cnt==n-1)
        return sum;
    return -1;
}
int main()
{
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
            char s[3];
            scanf("%s",s);
            if(s[0]=='R')
                e[i].col=0;
            else if(s[0]=='G')
                e[i].col=1;
            else
                e[i].col=2;
        }
        sort(e+1,e+m+1,cmp);
        memset(vis,0,sizeof(vis));
        int x=find(0,0,1);
        int y=find(1,1,2);
        printf("Case #%d:\n",t);
        for(int i=1;i<n-1;i++)
            printf("-1\n");
        if(x==-1)
        {
            if(y==-1)
            {
                for(int i=n-1;i<=m;i++)
                {
                    printf("-1\n");
                }
            }
            else
            {
                printf("%d\n",y);
                for(int j=1;j<=m;j++)
                {
                    if(!vis[1][j])
                    {
                        y+=e[j].c;
                        printf("%d\n",y);
                    }
                }
            }
        }
        else
        {
            if(y==-1)
            {
                printf("%d\n",x);
                for(int j=1;j<=m;j++)
                {
                    if(!vis[0][j])
                    {
                        x+=e[j].c;
                        printf("%d\n",x);
                    }
                }
            }
            else
            {
                printf("%d\n",min(x,y));
                for(int i=n;i<=m;i++)
                {
                    for(int j=1;j<=m;j++)
                    {
                        if(!vis[0][j])
                        {
                            vis[0][j]=1;
                            x+=e[j].c;
                            break;
                        }
                    }
                    for(int j=1;j<=m;j++)
                    {
                        if(!vis[1][j])
                        {
                            vis[1][j]=1;
                            y+=e[j].c;
                            break;
                        }
                    }
                    //printf("aaa  %d %d\n",x,y);
                    printf("%d\n",min(x,y));
                }
            }
        }
    }
    return 0;
}