P17808 [ICPC 2019 Nanchang R] Bob's Problem

Bob 遇到了麻烦。他摩擦了手指上的魔戒，于是你从地底冒了出来。 给定一个无向图 $G$，包含 $n$ 个顶点（编号 $1$ 到 $n$），以及 $m$ 条带权边，每条边被染成黑色或白色。你需要从 $G$ 中选择一些边，使得任意两个顶点之间都存在至少一条仅经过所选边的路径，同时你可以选择不超过 $k$ 条白边。满足条件的选边方案可能有多种，请你找出所选边总权重最大的一种方案。

第一行包含一个整数 $T$（$1\leq T\leq 5$），表示测试数据的组数。 对于每组测试数据，第一行包含三个整数 $n$（$1 \le n \le 50000$）、$m$ 和 $k$（$1\le k\le m \le 500000$）。 接下来的 $m$ 行，每行包含四个整数 $u, v$（$1\le u,v\le n$）、$w$（$0\le w\le 100000$）和 $c$（$0\le c\le 1$），描述一条连接第 $u$ 个顶点与第 $v$ 个顶点的边，其权重为 $w$，颜色为 $c$。若 $c = 1$，则该边为白色；若 $c = 0$，则为黑色。 注意，某些顶点之间可能存在多条边，图中也允许出现自环。

对于每组测试数据，输出一行一个整数，表示所选边的最大总权重；如果对于给定的图不存在合法方案，则输出 `-1`。

翻译由 DeepSeek V4 Pro 完成