#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>
#include <assert.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <bitset>
#include <vector>
using namespace std;

#define LL long long

#define fi first
#define se second
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define ls id<<1
#define rs id<<1|1
#define MID(a,b) (((a)+(b))>>1)
#define maxx(a,b) ((a)<(b)?(b):(a))
#define minx(a,b) ((a)<(b)?(a):(b))
#define absx(a) ((a)<0?-(a):(a))
#define mk(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define itr iterator
#define lowbit(x) ((x)&-(x))

typedef unsigned LL ULL;
typedef unsigned uint;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;

template< typename T > inline void read(T &x) {
    static bool fr_f; static char fr_ch;
    fr_f=0; x=0; fr_ch=getchar();
    while(fr_ch<'0' || '9'<fr_ch) {if(fr_ch=='-') fr_f=1; fr_ch=getchar();}
    while('0'<=fr_ch && fr_ch<='9') {x=(x<<1)+(x<<3)+fr_ch-'0'; fr_ch=getchar();}
    if(fr_f) x=-x;
}

template< typename T > inline void Max (T &a, T b) {if(a<b) a=b;}
template< typename T > inline void Min (T &a, T b) {if(b<a) a=b;}
template< typename T > inline void Swap(T &a, T &b) {T c=a;a=b;b=c;}
template< typename T > inline T Abs(T a) {if(a<0) return -a; else return a;}

const double   pi = acos(-1.0) ;
const int     MOD = (int)1e9+7 ;
const int     INF = (int)0x3f3f3f3f ;
const LL     LINF = (LL)INF<<32|INF ;
const int    SINF = (uint)(-1)>>1 ;
const LL    SLINF = (ULL)(-1)>>1 ;
const double DINF = 1e50 ;
const double  eps = 1e-8 ;
const int    maxn = (int) 1e5+20 ;
const int    maxm = (int) 1000+20 ;
const int    maxk = (int) 1000+20 ;

inline int sig(double x) {return x<-eps?-1:x>eps;}
inline LL fp(LL a,LL n,LL p) {LL res=1; for(;n;n>>=1,a=a*a%p) if(n&1) res=res*a%p; return res;}
template<typename T>inline T gcd(T a,T b) {for(T c;b;c=a%b,a=b,b=c); return a;}

//--------------------start--------------------

int n, m;

struct Edge
{
    int u,v,w;
};

vector<Edge> vec[3];

int fa[105];

int find_fa(int x)
{
//    cout <<x <<" " <<fa[x] <<endl;
    if(x == fa[x]) return x;
    return fa[x] = find_fa(fa[x]);
}

int ans[105];

int CMP(const Edge &x, const Edge &y)
{
    return x.w < y.w;
}

void go(vector<Edge> us, vector<Edge> fr)
{
//    cout <<us.size() <<" " <<fr.size() <<endl;
    sort(us.begin(), us.end(), CMP);

    for(int i = 1; i <= n; i++) fa[i] = i;

    int cnt = 0, val = 0;
    for(int i = 0; i < us.size(); i++)
    {
//        cout <<" " <<i <<endl;
        Edge e = us[i];
//        cout <<e.u <<" " <<e.v <<" " <<e.w <<endl;
        int xf = find_fa(e.u);
//        cout <<" " <<i <<endl;
        int yf = find_fa(e.v);

        if(xf == yf)
        {
            fr.pb(e);
        }
        else
        {
            cnt++;
            val += e.w;
            fa[xf] = yf;
        }
    }
//    cout <<cnt <<" " <<val <<endl;
    if(cnt == n - 1)
    {
        int tval = 0, i = n - 1, j = 0;
//        cout <<fr.size() <<endl;
        sort(fr.begin(), fr.end(), CMP);
        while(1)
        {
            Min(ans[i], val + tval);

            i++;
            if(i > m) break;
            if(j == fr.size()) break;
            tval += fr[j].w;
            j++;

//            cout <<"! :" <<i <<" " <<j <<endl;
        }
    }
}

void work()
{
    int tc; read(tc);
    int T_T = 0;
    while(tc--)
    {
        read(n), read(m);

        for(int i = 0; i < 3; i++) vec[i].clear();


        for(int i = 1; i <= m; i++) ans[i] = INF;

        int x, y, z;
        char type[3];
        Edge e;
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d%s", &x, &y, &z, type);
            e.u = x;
            e.v = y;
            e.w = z;
            if(type[0] == 'G')
            {
                vec[0].pb(e);
            }
            else if(type[0] == 'R')
            {
                vec[1].pb(e);
            }
            else
            {
                vec[2].pb(e);
            }
        }

        {
            vector<Edge> us, fr;

            for(int i = 0; i < vec[0].size(); i++) us.pb(vec[0][i]);
            for(int i = 0; i < vec[1].size(); i++) us.pb(vec[1][i]);

            for(int i = 0; i < vec[2].size(); i++) fr.pb(vec[2][i]);
            go(us, fr);
        }

        {
            vector<Edge> us, fr;

            for(int i = 0; i < vec[0].size(); i++) us.pb(vec[0][i]);
            for(int i = 0; i < vec[2].size(); i++) us.pb(vec[2][i]);

            for(int i = 0; i < vec[1].size(); i++) fr.pb(vec[1][i]);

            go(us, fr);
        }

        for(int i = 1; i <= m; i++) if(ans[i] == INF) ans[i] = -1;
        printf("Case #%d:\n", ++T_T);
        for(int i = 1; i <= m; i++)
            printf("%d\n", ans[i]);
    }
}


//---------------------end---------------------

int main()
{
#ifdef yukihana0416
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif // yukihana0416
    work();
    return 0;
}