P17808 [ICPC 2019 Nanchang R] Bob's Problem

Bob was in trouble. He rubbed the magic ring on his finger, and you came out of the ground. You are given an undirected graph $G$ which contains $n$ vertices labelled from $1$ to $n$, with $m$ weighted edges between them coloured in black or white. You have to choose some edges in $G$ such that there is at least one path between any two vertices only passing by selected edges, and you can select no more than $k$ white edges. There may be multiple available strategies to determine these edges, and you are asked to find out the way with a maximum total weight of edges.

The first line contains an integer $T$ ($1\leq T\leq 5$) indicating the number of test cases. For each test case, the first line contains three integers $n~(1 \le n \le 50000), m$ and $k~(1\le k\le m \le 500000)$. Each of the following $m$ lines contains four integers $u, v~(1\le u,v\le n), w~(0\le w\le 100000)$ and $c~(0\le c\le 1)$ describing an edge of weight $w$ and colour $c$ between the $u$-th vertex and the $v$-th vertex. Here an edge is white if $c = 1$, or black if $c = 0$. Note that there may be multiple edges between some vertices, and self-loops are also allowed.

For each test case, output a single line with an integer indicating the maximum total weight of selected edges, or output `-1` if there is no solution for the given graph.