#include <bits/stdc++.h>
#define X           first
#define Y           second
#define pb          push_back
#define mp          make_pair
#define SZ(X)       (X.size())
#define mst(a,b)    memset((a),(b),sizeof(a))
#define lowbit(a)   ((a)&(-a))
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int N = 5e5 + 10;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const LL INF = 1LL << 61;
const int maxn=100+10;
struct Edge{
    int u,v,w,type;
    Edge(int u=0,int v=0,int w=0,int type=0):u(u),v(v),w(w),type(type){}
    bool operator < (const Edge &rhs) const {
        return w<rhs.w;
    }
}edge[maxn];
int fa[maxn];
void init(){
    for (int i=1;i<=100;i++) fa[i]=i;
}
int Find(int x){
    return x==fa[x]?x:fa[x]=Find(fa[x]);
}
int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
#endif // local
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T,cas=1; cin>>T;
    while (T--){
        int n,m; cin>>n>>m;
        for (int i=0;i<m;i++){
            int u,v,w; char s[5];
            cin>>u>>v>>w>>s;
            int type;
            if (s[0]=='R') type=0; else if (s[0]=='G') type=1; else type=2;
            edge[i]=Edge(u,v,w,type);
        }
        sort(edge,edge+m);
        cout<<"Case #"<<cas++<<":\n";
        multiset<int> hehe,haha;
        init();
        int ans=0;
        for (int i=0;i<m;i++){
            hehe.insert(edge[i].w);
            if (edge[i].type>1) continue;
            int dx=Find(edge[i].u),dy=Find(edge[i].v);
            if (dx!=dy){
                ans+=edge[i].w;
                fa[dy]=dx;
                hehe.erase(hehe.find(edge[i].w));
            }
        }
        if (hehe.size()!=m-(n-1)) ans=inf;
        init();
        int res=0;
        for (int i=0;i<m;i++){
            haha.insert(edge[i].w);
            if (edge[i].type<1) continue;
            int dx=Find(edge[i].u),dy=Find(edge[i].v);
            if (dx!=dy){
                res+=edge[i].w;
                fa[dy]=dx;
                haha.erase(haha.find(edge[i].w));
            }
        }
        if (haha.size()!=m-(n-1)) res=inf;
        for (int i=1;i<=m;i++){
            if (i<n-1) cout<<-1<<"\n"; else {
                //cout<<ans<<" "<<res<<endl;
                int xx=min(ans,res);
                if (xx>=inf) xx=-1;
                cout<<xx<<"\n";
                if (hehe.size()){
                    int tmp=*hehe.begin();
                    ans+=tmp;
                    hehe.erase(hehe.begin());
                }
                if (haha.size()){
                    int tmp=*haha.begin();
                    res+=tmp;
                    haha.erase(haha.begin());
                }
            }
        }
    }
    return 0;
}