#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<"="<<x<<endl
#define fgx cerr<<"-------------"<<endl
#define N 1000000
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct E{int x,y,z;E(int _x=0,int _y=0,int _z=0):x(_x),y(_y),z(_z){}}e1[N],e2[N];
inline bool operator <(E x,E y){return x.z<y.z;}
priority_queue<int> q1,q2;
char c[10];int fa[N];
inline int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
int main()
{//    freopen("a.in","r",stdin);
//    freopen("a.out","w",stdout);
    int t; cin>>t;
    for(rint T=1;T<=t;T++)
    {    while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop();
        int n,m,n1=0,n2=0,t1=0,t2=0,ans1=0,ans2=0,x,y,z; scanf("%d%d",&n,&m);
        for(rint i=1;i<=m;i++)
        {    scanf("%d%d%d%s",&x,&y,&z,c+1);
            if(c[1]=='G'||c[1]=='R') e1[++n1]=E(x,y,z);
            if(c[1]=='G'||c[1]=='B') e2[++n2]=E(x,y,z);
            if(c[1]=='B') q1.push(-z); if(c[1]=='R') q2.push(-z);
        }
        sort(e1+1,e1+n1+1); sort(e2+1,e2+n2+1);
        for(rint i=1;i<=n;i++) fa[i]=i;
        for(rint i=1;i<=n1;i++)
        {    int x=findfa(e1[i].x),y=findfa(e1[i].y);
            if(x!=y) fa[x]=y,t1++,ans1+=e1[i].z;
            else q1.push(-e1[i].z);
        }
        for(rint i=1;i<=n;i++) fa[i]=i;
        for(rint i=1;i<=n2;i++)
        {    int x=findfa(e2[i].x),y=findfa(e2[i].y);
            if(x!=y) fa[x]=y,t2++,ans2+=e2[i].z;
            else q2.push(-e2[i].z);
        }
        printf("Case #%d:\n",T);
        if(t1!=n-1&&t2!=n-1){for(rint i=1;i<=m;i++) printf("-1\n");continue;}
        for(rint i=1;i<n-1;i++) printf("-1\n");
        if(t1!=n-1) ans1=1e9; if(t2!=n-1) ans2=1e9;
        printf("%d\n",min(ans1,ans2));
        for(rint i=n;i<=m;i++)
        {    ans1-=q1.top(); ans2-=q2.top(); q1.pop(); q2.pop();
            printf("%d\n",min(ans1,ans2));
        }
    }
    return 0;
}