#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 110;
const int inf = 0x3f3f3f3f;

struct node
{
    int u,v,w,id;
    char s[5];
    friend bool operator<( const node&a , const node&b )
    {
        return a.w<b.w;
    }
}a[maxn],b[maxn],c[maxn];
int n,m,tol,pre[maxn],va[maxn],vb[maxn];
int Find( int x )
{
    if ( x!=pre[x] )
        pre[x] = Find( pre[x] );
    return pre[x];
}
int kruskal( int flag )
{
    for ( int i=1 ; i<=n ; i++ )
        pre[i] = i;
    sort ( b+1 , b+tol+1 );
    int cnt = 0,ans = 0;
    for ( int i=1 ; i<=tol ; i++ )
    {
        int fx = Find( b[i].u );
        int fy = Find( b[i].v );
        if ( fx!=fy )
        {
            cnt++;
            ans += b[i].w;
            if ( flag )
                vb[b[i].id] = 1;
            else
                va[b[i].id] = 1;
            pre[fy] = fx;
        }
    }
    if ( cnt<n-1 )
        return inf;
    else
        return ans;
}

int main()
{
    for ( int T ; scanf ( "%d" , &T )==1 ; )
    {
        for ( int cas=1 ; cas<=T ; cas++ )
        {
            memset ( va , 0 , sizeof(va) );
            memset ( vb , 0 , sizeof(vb) );
            scanf ( "%d%d" , &n , &m );
            for ( int i=1 ; i<=m ; i++ )
                a[i].id = i,scanf ( "%d%d%d%s" , &a[i].u , &a[i].v , &a[i].w , a[i].s );
            tol = 0;
            for ( int i=1 ; i<=m ; i++ )
            {
                if ( a[i].s[0]!='B' )
                {
                    tol++;
                    b[tol] = a[i];
                }
            }
            int aa = kruskal( 0 );
            tol = 0;
            for ( int i=1 ; i<=m ; i++ )
            {
                if ( a[i].s[0]!='R' )
                {
                    tol++;
                    b[tol] = a[i];
                }
            }
            int bb = kruskal( 1 );
            int ans = min ( aa , bb );
            int tb = 0,tc = 0;
            for ( int i=1 ; i<=m ; i++ )
            {
                if ( !va[i] )
                    b[tb++] = a[i];
                if ( !vb[i] )
                    c[tc++] = a[i];
            }
            sort ( b , b+tb );
            sort ( c , c+tc );
            for ( int i=1 ; i<tb ; i++ )
                b[i].w += b[i-1].w;
            for ( int i=1 ; i<tc ; i++ )
                c[i].w += c[i-1].w;
            printf ( "Case #%d:\n" , cas );
            for ( int i=1 ; i<n-1&&i<=m ; i++ )
                printf ( "-1\n" );
            if ( ans==inf )
                for ( int i=n-1 ; i<=m ; i++ )
                    printf ( "-1\n" );
            else
            {
                printf ( "%d\n" , ans );
                for ( int i=0 ; i<m-n+1 ; i++ )
                    printf ( "%d\n" , min ( aa+b[i].w , bb+c[i].w ) );
            }
        }
    }
    return 0;
}