#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=110, inf=1e9;
struct poi{int x, y, w, pos;}q[3][maxn];
int n, m, T, x, y, z;
int fa[maxn], cnt[2], ans[maxn];
bool v[maxn];
char s[233];

template<typename T>
inline void read(T &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;    
}

bool operator < (poi a, poi b){return a.w<b.w;}

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

inline void update(int ty)
{
    for(int i=1;i<=n;i++) fa[i]=i;
    memset(v, 0, sizeof(v));
    sort(q[ty]+1, q[ty]+1+cnt[ty]);
    int cntt=0, Ans=0;
    for(int i=1;i<=cnt[ty];i++)
    {
        int fx=gf(q[ty][i].x), fy=gf(q[ty][i].y);
        if(fx==fy) continue;
        cntt++; Ans+=q[ty][i].w; v[q[ty][i].pos]=1;
        fa[fx]=fy;
    }
    for(int i=1;i<=n;i++) if(gf(1)!=gf(i)) return;
    ans[cntt]=min(ans[cntt], Ans);
    for(int i=cntt+1;i<=m;i++)
    {
        for(int j=1;j<=m;j++) 
        if(!v[q[2][j].pos])
        {
//            puts("Qwq");
            Ans+=q[2][j].w;
            v[q[2][j].pos]=1;
            break;    
        }
//        printf("%d %d\n", i, Ans);
        ans[i]=min(ans[i], Ans);
    }
}

int main()
{
    read(T); int cntt=0;
    while(T--)
    {
        read(n); read(m); cnt[0]=cnt[1]=0;
        for(int i=1;i<=m;i++) 
        {
            read(x); read(y); read(z);
            scanf("%s", s+1);
            q[2][i]=(poi){x, y, z, i};
            if(s[1]=='G') q[0][++cnt[0]]=(poi){x, y, z, i}, q[1][++cnt[1]]=(poi){x, y, z, i};
            else if(s[1]=='R') q[0][++cnt[0]]=(poi){x, y, z, i};
            else q[1][++cnt[1]]=(poi){x, y, z, i};
        }
        cntt++; printf("Case #%d:\n", cntt);
        sort(q[2]+1, q[2]+1+m);
        for(int i=1;i<=m;i++) ans[i]=inf;
        update(0); update(1);
        for(int i=1;i<=m;i++) printf("%d\n", ans[i]==inf?-1:ans[i]);
    }
}