#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f

using namespace std;

struct Edge {
  int s,t,v,kind;
  Edge() {}
  Edge(int a,int b,int c,int d):s(a),t(b),v(c),kind(d) {}
  bool operator < (const Edge & b) const {return v<b.v;}
};

Edge e[105];

namespace SETS {

int fa[105];

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

int find_father(int x) {
  return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
} 

void merge(int x,int y) {
  x=find_father(x);y=find_father(y);
  if (x==y) return;
  fa[x]=y;
} 

bool check(int x,int y) {
  x=find_father(x);y=find_father(y);
  return x!=y;
}

}

bool in[105];
int ans[105];

void solve(int n,int m,int t) {
  memset(in,0,sizeof(in));
  SETS::init(n);
  int cnt=0,s=0;
  for(int i=1;i<=m;i++)
    if ((e[i].kind==2||e[i].kind==t)&&SETS::check(e[i].s,e[i].t)) {
        cnt++;
        SETS::merge(e[i].s,e[i].t);
        s+=e[i].v;
        in[i]=1;
    }
  if (cnt<n-1) return;
  ans[cnt]=min(ans[cnt],s);
  for(int i=1;i<=m;i++)
    if (!in[i]) {
        s+=e[i].v;cnt++;
        ans[cnt]=min(ans[cnt],s);
    }
}

int main() {
  int cases;
  scanf("%d",&cases);
  for(int t=1;t<=cases;t++) {
      memset(ans,0x3f,sizeof(ans));
      int n,m;
      scanf("%d%d",&n,&m);
      for(int i=1;i<=m;i++) {
          int x,y,z;
          char str[5];
          scanf("%d%d%d%s",&x,&y,&z,str);
          if (str[0]=='R') e[i]=Edge(x,y,z,1);
          if (str[0]=='G') e[i]=Edge(x,y,z,2);
          if (str[0]=='B') e[i]=Edge(x,y,z,3);
      }
    sort(e+1,e+m+1);
    solve(n,m,1);
    solve(n,m,3);
    printf("Case #%d:\n",t);
    for(int i=1;i<=m;i++) printf("%d\n",(ans[i]<inf)?ans[i]:-1);
  }
  return 0;
}