#include <bits/stdc++.h>

using namespace std;

int t, n, m, aaa, bbb, ca, cb, qa, qb, a[100005], b[100005], w[100005], par[200005];
bool c[100005][5], cc;
vector<pair<int, int>> v;
int ta, tb, tc;

int find(int aa) {
    return par[aa] == aa ? aa : par[aa] = find(par[aa]);
}

int main() {
    scanf("%d", &t);
    for (int tt = 1; tt <= t; tt++) {
        v.clear();
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d%s", a + i, b + i, w + i, c[i]);
            a[i]--;
            b[i]--;
            v.push_back({w[i], i});
        }
        printf("Case #%d:\n", tt);
        for (int i = 1; i < n - 1; i++)
            printf("-1\n");
        sort(v.begin(), v.end());
        for (int i = n - 1; i <= m; i++) {
            aaa = bbb = ca = cb = 0;
            qa = qb = i - (n - 1);
            for (int j = 0; j < n * 2; j++)
                par[j] = j;
            for (auto p : v) {
                ta = p.second;
                cc = c[ta][0];
                if (cc != 'R' && (tb = find(a[ta])) != (tc = find(b[ta]))) {
                        par[tb] = tc;
                        aaa += w[ta];
                        ca++;
                } else if (qa) {
                    aaa += w[ta];
                    qa--;
                }
                if (cc != 'B' && (tb = find(a[ta] + n)) != (tc = find(b[ta] + n))) {
                    par[tb] = tc;
                    bbb += w[ta];
                    cb++;
                } else if (qb) {
                    bbb += w[ta];
                    qb--;
                }
            }
            if (ca != n - 1)
                aaa = INT_MAX;
            if (cb != n - 1)
                bbb = INT_MAX;
            aaa = min(aaa, bbb);
            if (aaa == INT_MAX)
                aaa = -1;
            printf("%d\n", aaa);
        }
    }
    return 0;
}