30007 - 三原色图

度度熊有一张 n 个点 m 条边的无向图，所有点按照 1,2,\cdots,n 标号，每条边有一个正整数权值以及一种色光三原色红、绿、蓝之一的颜色。

现在度度熊想选出恰好 k 条边，满足只用这 k 条边之中的红色边和绿色边就能使 n 个点之间两两连通，或者只用这 k 条边之中的蓝色边和绿色边就能使 n 个点之间两两连通，这里两个点连通是指从一个点出发沿着边可以走到另一个点。

对于每个 k=1,2,\cdots,m，你都需要帮度度熊计算选出恰好 k 条满足条件的边的权值之和的最小值。

第一行包含一个正整数 T，表示有 T 组测试数据。

接下来依次描述 T 组测试数据。对于每组测试数据：

第一行包含两个整数 n 和 m，表示图的点数和边数。

接下来 m 行，每行包含三个整数 a,b,w 和一个字符 c，表示有一条连接点 a 与点 b 的权值为 w、颜色为 c 的无向边。

保证 1 \le T \le 100，1 \le n,m \le 100，1 \le a,b \le n，1 \le w \le 1000，c \in {R,G,B}，这里 R,G,B 分别表示红色、绿色和蓝色。

对于每组测试数据，先输出一行信息 "Case #x:"（不含引号），其中 x 表示这是第 x 组测试数据，接下来 m 行，每行包含一个整数，第 i 行的整数表示选出恰好 i 条满足条件的边的权值之和的最小值，如果不存在合法方案，输出 -1，行末不要有多余空格。