//Δ_1006
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111;
int n,m,a[N],b[N],c[N],d[N];
int f[N],w[N],r[N];
int fnd(int x){
    if(f[x]==x)
        return x;
    return f[x]=fnd(f[x]);
}
vector<pair<int,int> > v;
vector<int> p;
void solve(int x){
    v.clear(),p.clear();
    int i,j,o,s=0,h=n;
    for(i=1;i<=n;i=i+1)
        f[i]=i;
    for(i=1;i<=m;i=i+1){
        w[i]=1e9;
        if(d[i]==x)
            p.push_back(c[i]);
        else
            v.push_back(make_pair(c[i],i));
    }
    sort(v.begin(),v.end());
    o=v.size();
    for(i=0;i<o;i=i+1){
        j=v[i].second;
        if(fnd(a[j])==fnd(b[j]))
            p.push_back(c[j]);
        else
            f[fnd(a[j])]=fnd(b[j]),s+=c[j],h--;
    }
    if(h>1)
        return;
    w[n-1]=s;
    sort(p.begin(),p.end());
    j=0;
    for(i=n;i<=m;i=i+1)
        w[i]=w[i-1]+p[j++];
}
int main()
{
    int tc,tt,i,j,x;
    char ch[5];
    scanf("%d",&tc);
    for(tt=1;tt<=tc;tt++){
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i=i+1){
            scanf("%d%d%d%s",a+i,b+i,c+i,ch);
            if(ch[0]=='G')
                d[i]=0;
            if(ch[0]=='R')
                d[i]=1;
            if(ch[0]=='B')
                d[i]=2;
        }
        cout<<"Case #"<<tt<<':'<<endl;
        solve(1);
        for(i=1;i<=m;i=i+1)
            r[i]=w[i];
        solve(2);
        for(i=1;i<=m;i=i+1)
            if(r[i]==1e9&&w[i]==1e9)
                r[i]=-1,w[i]=-1;
        for(i=1;i<=m;i=i+1)
            cout<<min(r[i],w[i])<<endl;
    }
    return 0;
}