#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

typedef long long llint;

const llint INF = 0x3f3f3f3f;

enum COLOR {
    COLOR_R = 1,
    COLOR_G = 2,
    COLOR_B = 4
};

struct Edge {
    int a, b, length;
    COLOR color;
};

COLOR color_to_enum(char c) {
    switch (c) {
        case 'R':
            return COLOR_R;
        case 'G':
            return COLOR_G;
        case 'B':
            return COLOR_B;
        default:
            print("error");
    }
}

class DisjointSet {
public:
    DisjointSet(int n_): n(n_), father(n_, 0) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    int find_father(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find_father(father[x]);
    }

    int make_union(int a, int b) {
        int fa = find_father(a);
        int fb = find_father(b);

        father[fa] = fb;
    }

    bool is_same_set(int a, int b) {
        int fa = find_father(a);
        int fb = find_father(b);

        return fa == fb;
    }

private:
    int n;
    vector<int> father;
};

struct Solution {
    int n, m;
    vector<Edge> edges;
    multiset<int> nonvisited[2];

    void init() {
        edges.resize(m);
    }

    int solve(int color, int idx) {
        int res = 0;
        DisjointSet ds(n + 1);
        for (int i = 0; i < m; i++) {
            const auto& edge = edges[i];
            if (!(edge.color & color)) {
                nonvisited[idx].insert(edge.length);
                continue;
            }

            if (ds.is_same_set(edge.a, edge.b)) {
                nonvisited[idx].insert(edge.length);
                continue;
            }

            ds.make_union(edge.a, edge.b);
            res += edge.length;
        }

        for (int i = 1; i <= n; i++) {
            if (ds.is_same_set(i, 1) == false) {
                return INF;
            }
        }

        return res;
    }

    int add_edge(int idx) {
        if (nonvisited[idx].empty()) {
            return INF;
        }
        int res = *nonvisited[idx].begin();
        nonvisited[idx].erase(nonvisited[idx].begin());
        return res;
    }
};

int main() {
    int T;
    int case_ = 1;
    input(T);
    while (T--) {
        printf("Case #%d:\n", case_++);

        Solution S;
        input(S.n >> S.m);
        S.init();

        int a, b, length;
        char color[5];
        for (int i = 0; i < S.m; i++) {
            scanf("%d%d%d%s", &a, &b, &length, color);
            COLOR color_enum = color_to_enum(color[0]);
            S.edges[i] = Edge{a, b, length, color_enum};
        }

        sort(S.edges.begin(), S.edges.end(), [](const Edge& e1, const Edge& e2) {
            return e1.length < e2.length;
        });

        llint res1 = S.solve(COLOR_R | COLOR_G, 0);
        llint res2 = S.solve(COLOR_B | COLOR_G, 1);

        for (int i = 1; i < S.n - 1; i++) {
            puts("-1");
        }

        if (res1 == INF && res2 == INF) {
            for (int i = S.n - 1; i <= S.m; i++) {
                puts("-1");
            }
            continue;
        }

        for (int i = S.n - 1; i <= S.m; i++) {
            print(min(res1, res2));
            res1 += S.add_edge(0);
            res2 += S.add_edge(1);
        }
    }
    return 0;
}