P16133 [ICPC 2018 NAIPC] Rainbow Graph

Roy 和 Biv 有一个 $n$ 个节点的无向图，节点编号为 $1 \dots n$。图中的每条边都有一个权重和一种颜色。权重是正整数。边的颜色恰好有三种：红色（Red）、绿色（Green）和蓝色（Blue）。同一对顶点之间可能存在多条边，图中甚至可能存在自环。 考虑如下任务（固定一个正整数 $k$）：Roy 和 Biv 希望恰好选择图中的 $k$ 条边，并删除所有其他边。他们希望这样选择后，仅凭所选出的 $k$ 条边，两人都能看到整个图是连通的。 然而，问题在于：Roy 看不见红色边，Biv 看不见蓝色边。因此，他们选择边的方式必须满足：仅用蓝色边和绿色边就足以使所有节点连通，并且仅用红色边和绿色边也足以使所有节点连通。对于 $k$ 从 $1$ 到总边数的每个取值，求出满足上述条件的所有 $k$ 条边的子集中，边权和的最小值。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100$），其中 $n$ 是图中的节点数，$m$ 是边数。 接下来的 $m$ 行，每行包含三个整数和一个字符：$a$、$b$（$1 \leq a, b \leq n$）、$w$（$1 \leq w \leq 1{,}000$）和 $c$（$c \in \{R, G, B\}$），表示节点 $a$ 和 $b$ 之间有一条权重为 $w$、颜色为 $c$ 的边（$R=$ 红色，$G=$ 绿色，$B=$ 蓝色）。

输出 $m$ 行，每行对应 $k = 1 \dots m$ 的结果。如果对于某个 $k$ 无法使 Roy 和 Biv 都看到图是连通的，则输出 $-1$；否则，输出满足条件的选择 $k$ 条边的子集的最小边权和。

翻译由 DeepSeek V3.2 完成