#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>

#define rep(i,e) for(int i=0;i<(e);i++)
#define rep1(i,e) for(int i=1;i<=(e);i++)
#define repx(i,x,e) for(int i=(x);i<=(e);i++)
#define pii pair<int,int>
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define mset(var,val) memset(var,val,sizeof(var))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

typedef long long ll;
template <class T>
void test(T a){cout<<a<<endl;}
template <class T,class T2>
void test(T a,T2 b){cout<<a<<" "<<b<<endl;}
template <class T,class T2,class T3>
void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;}
const int N = 2e3+10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;


int fa[N];
int faf(int x){
    if(x == fa[x]) return x;
    return fa[x] = faf(fa[x]);
}
bool Union(int x, int y){
    int xx = faf(x);
    int yy = faf(y);
    if(xx != yy){
        fa[xx] = yy;
        return true;
    }
    return false;
}

int ans[N];

struct E{
    int u, v, w;
    char c;
}e[N];

bool cmp(const E &a, const E &b){
    return a.w < b.w;
}

bool vis[N];

int T = 1;
void work(){
//    printf("Case #%d: ", T++);
    cout << "Case #" << T++ << ":" << endl;
    int n, m;
    cin >> n >> m;
    rep1(i,n){
        fa[i] = i;
    }
    rep(i,m){
        cin >> e[i].u >> e[i].v >> e[i].w >> e[i].c;
    }
    sort(e, e+m, cmp);
    mset(ans, -1);
    mset(vis, false);
    int st = 0;
    int now = 0;
    int block = n;
    rep(i,m){
        if(e[i].c == 'R' || e[i].c == 'G'){
            if(Union(e[i].u, e[i].v)){
                now += e[i].w;
                vis[i] = true;
                ++st;
                --block;
            }
        }
    }
    int i,j;
    if(block == 1){
        for(j = st, i = 0; i < m; ++i){
            if(~ans[j])
                ans[j] = min(ans[j], now);
            else
                ans[j] = now;
            if(vis[i]) continue;
            now += e[i].w;
            ++j;
        }
        if(~ans[j])
            ans[j] = min(ans[j], now);
        else
            ans[j] = now;
    }
    mset(vis,false);
    rep1(i,n) fa[i] = i;
    st = 0;
    now = 0;
    block = n;
    rep(i,m){
        if(e[i].c == 'B' || e[i].c == 'G'){
            if(Union(e[i].u, e[i].v)){
                now += e[i].w;
                vis[i] = true;
                ++st;
                --block;
            }
        }
    }
    if(block == 1){
        for(j = st, i = 0; i < m; ++i){
            if(~ans[j])
                ans[j] = min(ans[j], now);
            else
                ans[j] = now;
            if(vis[i]) continue;
            now += e[i].w;
            ++j;
        }
        if(~ans[j])
            ans[j] = min(ans[j], now);
        else
            ans[j] = now;
    }
    rep1(i,m){
        cout << ans[i] << endl;
    }
}

int main() {
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    IOS;
    int t;
//    scd(t);
    cin >> t;
    for(;t--;){
        work();
    }
//    work();
}