/* ***********************************************
Author        :yang12138
Created Time  :2018年08月04日 星期六 22时15分45秒
File Name     :1006.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)

const int N=105;

int fa[N];
void init(){
    for(int i=0;i<N;i++) fa[i]=i;
}

int find_fa(int u){
    return fa[u]=((fa[u]==u)?u:find_fa(fa[u]));
}

void update(int u,int v){
    u=find_fa(u);
    v=find_fa(v);
    fa[u]=v;
}

struct Edge{
    int u,v,w,id;
    char c;
    bool operator < (const Edge& tmp)const{
        return w<tmp.w;
    }
}e[N];

int dat[N];
int n,m;
bool vis[N];
bool ban[N];
const int INF=1e9;

int mst(){
    int ans=0,cnt=0;
    init();
    for(int i=1;i<=m;i++){
        if(ban[i]) continue;
        int u=e[i].u,v=e[i].v;
        if(find_fa(u)==find_fa(v)) continue;
        update(u,v);
        ans+=e[i].w;
    }
    return ans;
}

bool check(){
    for(int i=2;i<=n;i++){
        if(find_fa(i)!=find_fa(i-1)) return 0;
    }
    return 1;
}

vector<int> cal(char ch){
    vector<int>ve;

    for(int i=n-1;i<=m;i++){
        memset(ban,0,sizeof(ban));
        int sum=0,cnt=i-n+1;
        init();
        for(int j=1;j<=cnt;j++){
            sum+=e[j].w;
            if(e[j].c==ch) continue;
            int u=e[j].u,v=e[j].v;
            update(u,v);
        }
        int left=n-1;
        memset(vis,0,sizeof(vis));
        for(int j=cnt+1;j<=m;j++){
            if(e[j].c==ch) continue;
            int u=e[j].u,v=e[j].v;
            if(find_fa(u)==find_fa(v)) continue;
            update(u,v),left--,sum+=e[j].w,vis[j]=1;
        }
        for(int j=cnt+1;j<=m && left;j++){
            if(!vis[j]) left--,sum+=e[j].w;
        }
        if(!check()) return vector<int>(N,INF);
        ve.push_back(sum);
    }
    return ve;
}

void solve(int t){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    //    scanf("%d %d %d %c",&e[i].u,&e[i].v,&e[i].w,&e[i].c);
        cin>>e[i].u>>e[i].v>>e[i].w>>e[i].c;
        e[i].id=i;
        dat[i]=e[i].w;
    }
    sort(e+1,e+m+1);

    printf("Case #%d:\n",t);

    if(m<n-1){
        for(int i=1;i<=m;i++) printf("-1\n");
        return ;
    }

    for(int i=1;i<n-1;i++) printf("-1\n");
    vector<int>ve[2];
    ve[0]=cal('B');
    ve[1]=cal('R');
    for(int i=n-1;i<=m;i++){
        int ans=min(ve[0][i-n+1],ve[1][i-n+1]);
        if(ans==INF) ans=-1;
        printf("%d\n",ans);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    
    int T,t=0;
    cin>>T;
    while(T--) solve(++t);
    return 0;
}