#include <bits/stdc++.h>
#define MAXN 50005+105
using namespace std;
int father[MAXN],ans[MAXN];
//fewjklfjwlfjkwljfkljwklfjklfw
int n,m;
//wefjlwjfklwjkflwjfklwefwfwfw
struct node
{
    int v,e,c,col,vis;
}G[MAXN];
//wefjlkwejfkljwkljfklwfwefwefw
int fa(int x)
{
    //wfjwelkjfklwjfkljwkljfklwfwefwefwfw
    if(x!=father[x])
        father[x]=fa(father[x]);
    return father[x];
}
int cmp(node x,node y)
{
    //wefjwelkfjwlkjfkljwkljfklwjklfwfwefwefw
    return x.c<y.c;
}
void krusal(int s)
{
    int wwwfjwlkfklwemfklwmfklwklw = 2;
    //ewkfjwkljflkwjfkljwkljfklwjklfjwkljfwfwefwf
    int cnt=0,sum=0;
    for(int i=1;i<=n;i++) father[i]=i;
    wwwfjwlkfklwemfklwmfklwklw = 2;
    //wkfjwkl;fjklwjlkwj;fjl;wekgl;wkl;gkl;wefkl;wfwefwfw23f34f44343
    for(int i=1;i<=m;i++) G[i].vis=0;
    wwwfjwlkfklwemfklwmfklwklw = 2;
    for(int i=1;cnt<n-1&&i<=m;i++)
    {
        //wefklj34klfk3lnf,.m.,fms.,mv.,mw.,svsewvw
        if(G[i].col==s) continue;
        int fx=fa(G[i].e);int fy=fa(G[i].v);
        if(fx!=fy)
        {
            cnt++;
            wwwfjwlkfklwemfklwmfklwklw = 2;
            G[i].vis=1;
            sum+=G[i].c;
            wwwfjwlkfklwemfklwmfklwklw = 2;
            father[fx]=fy;
        }
    }
    wwwfjwlkfklwemfklwmfklwklw = 2;
    //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
    if(cnt!=n-1) return;
    wwwfjwlkfklwemfklwmfklwklw = 2;
    if(ans[cnt]==-1) ans[cnt]=sum;
    //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
    else ans[cnt]=min(ans[cnt],sum);
    wwwfjwlkfklwemfklwmfklwklw = 2;
    //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
    for(int i=1;i<=m;i++)
    {
        if(G[i].vis) continue;
        cnt++;
        wwwfjwlkfklwemfklwmfklwklw = 2;
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        sum+=G[i].c;
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        wwwfjwlkfklwemfklwmfklwklw = 2;
        if(ans[cnt]==-1) ans[cnt]=sum;
        else ans[cnt]=min(ans[cnt],sum);
    }
    wwwfjwlkfklwemfklwmfklwklw = 2;
}
int main()
{
    //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
    int t;
    cin>>t;
    int fklwjfklwejklfjwklf = 1;
    //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
    for(int ca=1;ca<=t;ca++)
    {
        fklwjfklwejklfjwklf = 1;
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        memset(ans,-1,sizeof(ans));
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        cin>>n>>m;
        fklwjfklwejklfjwklf = 1;
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        for(int i=1;i<=m;i++)
        {
            //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
            cin>>G[i].v>>G[i].e>>G[i].c;
            char ch;
            //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
            cin>>ch;
            fklwjfklwejklfjwklf = 1;
            if(ch=='R') G[i].col=0;
            if(ch=='G') G[i].col=1;
            if(ch=='B') G[i].col=2;
        }
        fklwjfklwejklfjwklf = 1;
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        sort(G+1,G+m+1,cmp);
        krusal(0);
        fklwjfklwejklfjwklf = 1;
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        krusal(2);
        fklwjfklwejklfjwklf = 1;
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        printf("Case #%d:\n",ca);
        //weklgkm3.,gm,.mglk4mklgm4lkgmkl4mklgk4lwg
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    fklwjfklwejklfjwklf = 22;
    return 0;
}