Description

You are given an undirected, weighted, connected graph. Each edge is colored black or white. Find a minimum-total-weight spanning tree that contains exactly $need$ white edges.

It is guaranteed that a solution exists.

Input Format

The first line contains $V, E, need$, the numbers of vertices, edges, and the required number of white edges.

Then follow $E$ lines. Each line contains $s, t, c, col$, denoting the endpoints (vertices are numbered from $0$), the edge weight, and the color ($0$ for white, $1$ for black).

Output Format

Output one line: the total weight of the required spanning tree.

2 2 1
0 1 1 1
0 1 2 0

2

Hint

Constraints:

• For $5\%$ of the testdata, $V \le 10$.
• For another $15\%$ of the testdata, $V \le 15$.
• For $100\%$ of the testdata, $V \le 5 \times 10^4, E \le 10^5$.
• All edge weights are positive integers in $[1, 100]$.

By WJMZBMR.

Translated by ChatGPT 5