#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define INF 0X3F3F3F3F
#define N 205
#define M 200005
#define LL long long
#define ULL unsigned long long
#define FF(i, a, b) for(int i = a; i <= b; ++i)
#define RR(i, a, b) for(int i = a; i >= b; --i)
#define FJ(i, a, b) for(int i = a; i < b; ++i)
#define SC(x) scanf("%d", &x)
#define SCC(x, y) scanf("%d%d", &x, &y)
#define SCCC(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define SS(x) scanf("%s", x)
#define PR(x) printf("%d\n", x)
#define PII pair<int, int>
#define PLL pair<unsigned long long, unsigned long long>
#define MP make_pair
#define PB push_back
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
using namespace std;
inline void II(int &n){char ch = getchar(); n = 0; bool t = 0;
for(; ch < '0'; ch = getchar()) if(ch == '-') t = 1;
for(; ch >= '0'; n = n * 10 + ch - '0', ch = getchar()); if(t) n =- n;}
inline void OO(int a){if(a < 0) {putchar('-'); a = -a;}
if(a >= 10) OO(a / 10); putchar(a % 10 + '0');}
const long double eps = 1e-8;
int sgn(long double x){
    return (x > eps) - (x < -eps);
}
int n, m, u, v, w;
char c;
struct T{
    int u, v, w, c;
    bool operator < (const T &rhs)const {
        return w < rhs.w;
    }
}e[N];
int f[N], vis1[N], vis2[N], s1[N], s2[N];
int get(int k){
    return f[k] == k ? k : f[k] = get(f[k]);
}
int main(){
    //IN;
    int _; SC(_);
    FF(CA, 1, _){
        SCC(n, m);
        FF(i, 1, n) f[i] = i;
        FF(i, 1, m){
            scanf("%d %d %d %c", &e[i].u, &e[i].v, &e[i].w, &c);
            switch(c){
            case 'R':
                e[i].c = 1;
                break;
            case 'G':
                e[i].c = 2;
                break;
            case 'B':
                e[i].c = 3;
                break;
            }
        }
        printf("Case #%d:\n", CA);
        if(n == 1){
            FF(i, 1, m) puts("0");
            continue;
        }
        memset(vis1, 0, sizeof vis1);
        memset(vis2, 0, sizeof vis2);
        sort(e + 1, e + 1 + m);
        int ans1 = 0;
        int h1 = 0, h2 = 0;
        FF(i, 1, m) if(e[i].c < 3){
            int fu = get(e[i].u), fv = get(e[i].v);
            if(fu != fv){
                ++h1;
                ans1 += e[i].w;
                f[fu] = fv;
                vis1[i] = 1;
            }
        }
        FF(i, 1, n) f[i] = i;
        int ans2 = 0;
        FF(i, 1, m) if(e[i].c > 1){
            int fu = get(e[i].u), fv = get(e[i].v);
            if(fu != fv){
                ++h2;
                ans2 += e[i].w;
                f[fu] = fv;
                vis2[i] = 1;
            }
        }
        memset(s1, 0x3f, sizeof s1);
        memset(s2, 0x3f, sizeof s2);
        if(h1 == n - 1){
            int t = n - 1;
            s1[t] = ans1;
            FF(i, 1, m) if(!vis1[i]){
                ans1 += e[i].w;
                s1[++t] = ans1;
            }
        }
        if(h2 == n - 1){
            int t = n - 1;
            s2[t] = ans2;
            FF(i, 1, m) if(!vis2[i]){
                ans2 += e[i].w;
                s2[++t] = ans2;
            }
        }
        FF(i, 1, m){
            int t = min(s1[i], s2[i]);
            if(t == INF)puts("-1");
            else printf("%d\n", t);
        }
    }

    return 0;
}