#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int MAXN = 105;
const int MAXM = 1005;
int F1[MAXN],F2[MAXN];
priority_queue<int, vector<int>, greater<int> > q1,q2;
int n,m;
struct Edge{
    int u,v,w;
    bool used;
    int col;
}edge1[MAXM],edge2[MAXM];
int tot1,tot2;
void addedge1(int u,int v,int w,int col)
{
    edge1[tot1].used = false;
    edge1[tot1].col = col;
    edge1[tot1].u = u;
    edge1[tot1].v = v;
    edge1[tot1++].w = w;
}
void addedge2(int u,int v,int w,int col)
{
    edge2[tot2].used = false;
    edge2[tot2].col = col;
    edge2[tot2].u = u;
    edge2[tot2].v = v;
    edge2[tot2++].w = w;
}
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int find1(int x)
{
    if(F1[x] == -1) return x;
    else return F1[x] = find1(F1[x]);
}
int find2(int x)
{
    if(F2[x] == -1) return x;
    else return F2[x] = find2(F2[x]);
}
int Kruskal1()
{
    memset(F1,-1,sizeof(F1));
    sort(edge1,edge1+tot1,cmp);
    int cnt = 0;
    int ans = 0;
    for(int i=0;i<tot1;i++){
        int u = edge1[i].u;
        int v = edge1[i].v;
        int w = edge1[i].w;
        int t1 = find1(u);
        int t2 = find1(v);
        if(t1!=t2 && cnt<n-1 && edge1[i].col!=3){
            ans += w;
            F1[t1] = t2;
            cnt++;
        }
        else{
            q1.push(edge1[i].w);
        }
    }
    if(cnt < n-1) return INF;
    else return ans;
}
int Kruskal2()
{
    memset(F2,-1,sizeof(F2));
    sort(edge2,edge2+tot2,cmp);
    int cnt = 0;
    int ans = 0;
    for(int i=0;i<tot2;i++){

        int u = edge2[i].u;
        int v = edge2[i].v;
        int w = edge2[i].w;
        int t1 = find2(u);
        int t2 = find2(v);
        if(t1!=t2 && cnt<n-1 && edge2[i].col!=1){
            ans += w;
            F2[t1] = t2;
            cnt++;
        }
        else{
            q2.push(edge2[i].w);
        }
    }
    if(cnt < n-1) return INF;
    else return ans;
}
int main()
{
    int T;
    int kas = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        tot1 = tot2 = 0;
        for(int i=0;i<m;i++){
            int u,v,w;
            char c;
            scanf("%d%d%d %c",&u,&v,&w,&c);
            if(c == 'R'){
                addedge1(u,v,w,1);
                addedge2(u,v,w,1);
            }
            else if(c == 'G'){
                addedge1(u,v,w,2);
                addedge2(u,v,w,2);
            }
            else{
                addedge2(u,v,w,3);
                addedge1(u,v,w,3);
            }
        }
        printf("Case #%d:\n",kas++);
        int ans1,ans2;
        for(int k=1;k<=m;k++){
            if(k<n-1){
                printf("-1\n");
                continue;
            }
            if(k == n-1){
                ans1 = Kruskal1();
                ans2 = Kruskal2();
                int ans = min(ans1,ans2);
                if(ans == INF)
                    printf("-1\n");
                else
                    printf("%d\n", ans);
                continue;
            }
            if(!q1.empty() && ans1!=INF){
                ans1 += q1.top();
                q1.pop();
            }
            if(!q2.empty() && ans2!=INF){
                ans2 += q2.top();
                q2.pop();
            }
            int ans = min(ans1,ans2);
            if(ans == INF)
                printf("-1\n");
            else
                printf("%d\n", ans);
        }
    }
    return 0;
}