#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN = 205;
struct edge
{
      int a, b;
      int val;
      int c;
      bool operator<(const edge & obj)const
      {
            return val < obj.val;
      }
};
edge A[MAXN];
int fR[MAXN];
int fB[MAXN];
      int father[MAXN];
      int find(int x)
      {
            if (x != father[x])
                  father[x] = find(father[x]);
            return father[x];
      }
      void kruskal(int n, int m, int forbidden,int out[MAXN])
      {
            int i, t;
            int res = 0;
            int p=n;
            memset(out,-1,sizeof(out[0])*m);
            for (i = 0; i <= n; i++) father[i] = i;
            for(i=t=0;i<m;i++)
            {
                 if(A[i].c==forbidden||find(A[i].a) == find(A[i].b))
                 {
                        out[p++]=A[i].val;
                 }else
                 {
                     //  printf("use[%d] %d %d %d %c\n",i,A[i].a,A[i].b,A[i].val,A[i].c);
                        res += A[i].val;
                        father[find(A[i].a)] = find(A[i].b);
                        t++;
                 }
            }
            if(t<n-1)
            {
                memset(out,-1,sizeof(out[0])*(1+m));
            }else
            {
                out[n-1]=res;
                for(i=n;i<=m;i++)
                {
                    out[i]+=out[i-1];
                }
            }
      }

int main()
{
    int cas,n,m,i,t;
    char s[4];
        memset(fB,-1,sizeof(fB));
        memset(fR,-1,sizeof(fR));
    scanf("%d",&cas);
    for(t=1;t<=cas;t++)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d%s",&A[i].a,&A[i].b,&A[i].val,s);
            A[i].c=toupper(s[0]);
        }
        sort(A,A+m);
        kruskal(n,m,'R',fR);
        kruskal(n,m,'B',fB);
        printf("Case #%d:\n",t);
        for(i=1;i<=m;i++)
        {
            if(fR[i]==-1)
                printf("%d\n",fB[i]);
            else if(fB[i]==-1)
                printf("%d\n",fR[i]);
            else
                printf("%d\n",min(fR[i],fB[i]));
        }
    }
    return 0;
}