#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

struct node
{
    int u,v;
    int value,num;
    int flag;
} edge[1100];

int n,m;
int pre[110];
int resultR[1100],resultB[1100];
bool cmp(node a,node b)
{
    return a.value < b.value;
}

int Find(int x)
{
    return pre[x] == 0?x:pre[x] = Find(pre[x]);
}

void Union(int x,int y)
{
    int Fx = Find(x);
    int Fy = Find(y);
    if(Fx != Fy)
    {
        pre[Fx] = Fy;
    }
}
bool visR[1100],visB[1100];
int  Kuras(int limit,bool * vis)
{
    int ans = 0;
    int num = 0;
    memset(pre,0,sizeof(pre));
    for(int i = 0; i<m; i++)
    {
        if(edge[i].flag != limit && Find(edge[i].u) != Find(edge[i].v))
        {
            vis[edge[i].num] = true;
            ans += edge[i].value;
            Union(edge[i].u,edge[i].v);
            num++;
        }
        if(num == n-1)
        {
            return ans;
        }
    }
    ans = INF;
    return ans;
}
int main()
{
    int T;
    char s[2];
    scanf("%d",&T);
    for(int Case = 1; Case <= T; Case ++)
    {
        scanf("%d %d",&n,&m);
        for(int i = 0; i<m; i++)
        {
            scanf("%d %d %d %s",&edge[i].u,&edge[i].v,&edge[i].value,s);
            if(s[0] == 'R')
                edge[i].flag = 1;
            else if(s[0] == 'G')
                edge[i].flag = 2;
            else if(s[0] == 'B')
                edge[i].flag = 3;
        }
        sort(edge,edge+m,cmp);
        for(int i = 0; i<m; i++)
        {
            edge[i].num = i;
        }
        memset(visB,false,sizeof(visB));
        memset(visR,false,sizeof(visR));
        int ansR = Kuras(3,visR);
        int ansB = Kuras(1,visB);
        memset(resultR,INF,sizeof(resultR));
        memset(resultB,INF,sizeof(resultB));
        int k = n-1;
        resultR[k] = ansR;
        resultB[k] = ansB;
        for(int i = 0; i<m; i++)
        {
            if(!visR[i])
            {
                resultR[k+1] = min(resultR[k+1],resultR[k]+edge[i].value);
                k++;
            }

        }
        k = n-1;
        for(int i = 0; i<m; i++)
        {
           if(!visB[i])
            {
                resultB[k+1] = min(resultB[k+1],resultB[k]+edge[i].value);
                k++;
            }
        }

        printf("Case #%d:\n",Case);
        for(int i = 1; i<=m; i++)
        {
            int re = min(resultR[i],resultB[i]);

            if(re >= INF)
                printf("-1\n");
            else
                printf("%d\n",re);
        }
    }

    return 0;
}