#include <bits/stdc++.h>

using namespace std;
const int maxn = 120;
struct node {
    int u, v, val;
    char col;
    bool operator < (const node &rhs) const {
        return val < rhs.val;
    }
} a[maxn];
int f1[maxn], f2[maxn], sum1 = 0, sum2 = 0, val1 = 0, val2 = 0;
int find(int *f, int x) {
    return f[x] == x ? x : f[x] = find(f, f[x]);
}

int mix(int *f, int x, int y) {
    int fx = find(f, x), fy = find(f, y);
    if (fx == fy) {
        return 0;
    }
    f[fx] = fy;
    return 1;
}
queue <int> Q1, Q2;
int ans[maxn];
int main() {
    int T;
    scanf("%d", &T);
    for (int c = 1; c <= T; c++) {
        memset(ans, 0x3f, sizeof(ans));
        while (!Q1.empty()) {
            Q1.pop();
        }
        while (!Q2.empty()) {
            Q2.pop();
        }
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            f1[i] = f2[i] = i;
        }
        sum1 = sum2 = 1;
        val1 = val2 = 0;
        int num1 = 0, num2 = 0;
        for (int i = 0; i < m; i++) {
            char temp[3];
            scanf("%d%d%d%s", &a[i].u, &a[i].v, &a[i].val, temp);
            a[i].col = temp[0];
//            printf("%d %d %d %c\n", a[i].u, a[i].v, a[i].val, a[i].col);
        }
        sort(a, a + m);
        for (int i = 0; i < m; i++) {
            if (a[i].col == 'G') {
                if (sum1 < n) {
                    if (mix(f1, a[i].u, a[i].v)) {
                        sum1++;
                        val1 += a[i].val;
                        num1++;
                    } else {
                        Q1.push(a[i].val);
                    }
                    if (sum1 == n) {
                        ans[num1 - 1] = min(ans[num1 - 1], val1);
                        while (!Q1.empty()) {
                            val1 += Q1.front();
                            Q1.pop();
                            ans[num1] = min(ans[num1], val1);
                            num1++;
                        }
                    }
                } else {
                    while (!Q1.empty()) {
                        val1 += Q1.front();
                        Q1.pop();
                        ans[num1] = min(ans[num1], val1);
                        num1++;
                    }
                    val1 += a[i].val;
                    ans[num1] = min(ans[num1], val1);
                    num1++;
                }
                if (sum2 < n) {
                    if (mix(f2, a[i].u, a[i].v)) {
                        sum2++;
                        val2 += a[i].val;
//                        printf("red %d\n", a[i].val);
                        num2++;
                    } else {
                        Q2.push(a[i].val);
                    }
                    if (sum2 == n) {
//                        printf("%d\n", val2);
                        ans[num2 - 1] = min(ans[num2 - 1], val2);
                        while (!Q2.empty()) {
                            val2 += Q2.front();
                            Q2.pop();
                            ans[num2] = min(ans[num2], val2);
                            num2++;
                        }
                    }
                } else {
                    while (!Q2.empty()) {
                        val2 += Q2.front();
                        Q2.pop();
                        ans[num2] = min(ans[num2], val2);
                        num2++;
                    }
                    val2 += a[i].val;
                    ans[num2] = min(ans[num2], val2);
                    num2++;
                }
            } else if (a[i].col == 'B') {
                if (sum1 < n) {
                    if (mix(f1, a[i].u, a[i].v)) {
                        sum1++;
                        val1 += a[i].val;
                        num1++;
                    } else {
                        Q1.push(a[i].val);
                    }
                    if (sum1 == n) {
                        ans[num1 - 1] = min(ans[num1 - 1], val1);
                        while (!Q1.empty()) {
                            val1 += Q1.front();
                            Q1.pop();
                            ans[num1] = min(ans[num1], val1);
                            num1++;
                        }
                    }
                } else {
                    while (!Q1.empty()) {
                        val1 += Q1.front();
                        Q1.pop();
                        ans[num1] = min(ans[num1], val1);
                        num1++;
                    }
                    val1 += a[i].val;
                    ans[num1] = min(ans[num1], val1);
                    num1++;
                }
                Q2.push(a[i].val);
            } else if (a[i].col == 'R') {
                if (sum2 < n) {
                    if (mix(f2, a[i].u, a[i].v)) {
                        sum2++;
                        val2 += a[i].val;
//                        printf("red %d\n", a[i].val);
                        num2++;
                    } else {
                        Q2.push(a[i].val);
                    }
                    if (sum2 == n) {
                        ans[num2 - 1] = min(ans[num2 - 1], val2);
                        while (!Q2.empty()) {
                            val2 += Q2.front();
                            Q2.pop();
                            ans[num2] = min(ans[num2], val2);
                            num2++;
                        }
                    }
                } else {
                    while (!Q2.empty()) {
                        val2 += Q2.front();
                        Q2.pop();
                        ans[num2] = min(ans[num2], val2);
                        num2++;
                    }
                    val2 += a[i].val;
                    ans[num2] = min(ans[num2], val2);
                    num2++;
                }
                Q1.push(a[i].val);
            }
        }
        if (sum1 == n) {
            while (!Q1.empty()) {
                val1 += Q1.front();
                Q1.pop();
                ans[num1] = min(ans[num1], val1);
                num1++;
            }
        }
        if (sum2 == n) {
            while (!Q2.empty()) {
                val2 += Q2.front();
                Q2.pop();
                ans[num2] = min(ans[num2], val2);
                num2++;
            }
        }
        printf("Case #%d:\n", c);
        for (int i = 0; i < m; i++) {
            printf("%d\n", ans[i] == 0x3f3f3f3f ? -1 : ans[i]);
        }
    }
    return 0;
}