#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define re register
#define rep(i,s,t) for(re int i=s;i<=t;++i)
using namespace std;
#define gi(x) read(x)
#define gii(x,y) read(x),read(y)
#define giii(x,y,z) read(x),read(y),read(z)
#define ms(f,x) memset(f,x,sizeof f)
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
namespace IO{
    #define gc getchar()
    #define pc(x) putchar(x)
    template<typename T>inline void read(T &x){
        x=0;int f=1;char ch=gc;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=gc;}
        while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc;x*=f;return;
    }
    template<typename T>inline void write(T x=0){
        T wr[51];wr[0]=0;if(x<0)pc('-'),x=-x;if(!x)pc(48);
        while(x)wr[++wr[0]]=x%10,x/=10;while(wr[0])pc(48+wr[wr[0]--]);return;
    }
}
using IO::read;
using IO::write;
const int N=5e5+11;
struct edge{
    int x,y,z;
    char col[6];
    inline void in(){
        giii(x,y,z);
        scanf("%s",col);
    }
    inline bool operator<(edge A)const{
        return z<A.z;
    }
}e[N],t[N];
bool vis[N];
int fa[N],tot;
ll ans[N],sum;
const ll inf=(1ll<<60);
inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int T,n,m;
int main(){
    gi(T);
    rep(p,1,T){
        gii(n,m);
        rep(i,1,m)
            e[i].in();
        tot=0,sum=0;
        sort(e+1,e+m+1);
        int x,y;
        rep(i,1,n)
            fa[i]=i;
        rep(i,1,m)
            vis[i]=0,ans[i]=inf;
        rep(i,1,m)
            if(e[i].col[0]=='R'||e[i].col[0]=='G'){
                x=find(e[i].x),y=find(e[i].y);
                if(x==y)continue;
                vis[i]=1;
                fa[x]=y;
                ++tot;
                sum+=e[i].z;
                if(tot==n-1){
                    ans[n-1]=min(ans[n-1],sum);
                    break;
                }
            }
        if(tot==n-1){
            rep(i,1,m)
                if(!vis[i]){
                    ++tot;
                    sum+=e[i].z;
                    ans[tot]=min(ans[tot],sum);
                }
        }
        tot=0,sum=0;
        rep(i,1,n)
            fa[i]=i;
        rep(i,1,m)
            vis[i]=0;
        rep(i,1,m)
            if(e[i].col[0]=='B'||e[i].col[0]=='G'){
                x=find(e[i].x),y=find(e[i].y);
                if(x==y)continue;
                vis[i]=1;
                fa[x]=y;
                ++tot;
                sum+=e[i].z;
                if(tot==n-1){
                    ans[n-1]=min(ans[n-1],sum);
                    break;
                }
            }
        if(tot==n-1){
            rep(i,1,m)
                if(!vis[i]){
                    ++tot;
                    sum+=e[i].z;
                    ans[tot]=min(ans[tot],sum);
                }
        }
        printf("Case #%d:\n",p);
        rep(i,1,m)
            if(ans[i]==inf)
                puts("-1");
            else
                printf("%lld\n",ans[i]);
        
    }
    return 0;
}