当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6349：三原色图

题目描述
度度熊有一张 $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 \leq T \leq 100$，$1 \leq n,m \leq 100$，$1 \leq a,b \leq n$，$1 \leq w \leq 1000$，$c \in \{R,G,B\}$，这里 $R,G,B$ 分别表示红色、绿色和蓝色。
输出解释
对于每组测试数据，先输出一行信息 "Case #x:"（不含引号），其中 x 表示这是第 $x$ 组测试数据，接下来 $m$ 行，每行包含一个整数，第 $i$ 行的整数表示选出恰好 $i$ 条满足条件的边的权值之和的最小值，如果不存在合法方案，输出 $-1$，行末不要有多余空格。
输入样例 
1
5 8
1 5 1 R
2 1 2 R
5 4 5 R
4 5 3 G
1 3 3 G
4 3 5 G
5 4 1 B
1 2 2 B
输出样例 
Case #1:
-1
-1
-1
9
10
12
17
22
来自杭电HDUOJ的附加信息
Recommend chendu
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2018"百度之星"程序设计大赛 - 资格赛
源链接： HDU-6349
最后修改于 2020-10-25T23:30:32+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
1500/1000MS(Java/Others) 262144/262144K(Java/Others)