Minimum Spanning Tree with Exactly k White Edges

You are given an undirected weighted connected graph with n vertices and m edges. Each edge is colored either black or white. Your task is to find a spanning tree (a tree that connects all vertices) with exactly need white edges and with the minimum total weight.

The total weight of a spanning tree is defined as the sum of the weights of its edges. It is guaranteed that there exists at least one spanning tree satisfying the condition.

Mathematical Formulation:
Find a spanning tree T such that $$ \#\{e \in T \mid \text{color}(e)=\text{white}\} = need, $$ which minimizes $$ \sum_{e \in T} w(e). $$

Hint: A common approach to solving such a constrained optimization problem is to use Lagrange multipliers (or penalty methods) combined with binary search. For a parameter \(\lambda\), define the modified cost of an edge as $$ \text{cost}'(e)=w(e)+\lambda \cdot I_{\{e \text{ is white}\}}, $$ where \(I_{\{e \text{ is white}\}}=1\) if the edge is white and 0 otherwise. Then, running a standard Minimum Spanning Tree algorithm (e.g. Kruskal's) on the graph with these modified costs gives a spanning tree T whose number of white edges is a monotonic function of \(\lambda\). This observation can be used to binary search for \(\lambda\) that yields a spanning tree with exactly \(need\) white edges, and then recover the original cost.

inputFormat

The first line contains three integers n, m and need — the number of vertices, the number of edges, and the required number of white edges in the spanning tree.

The following m lines each contain an edge description with four entries: two integers u and v (the endpoints of the edge), an integer w (the weight of the edge), and a character C indicating the color of the edge. C will be either 'W' for white or 'B' for black. It is guaranteed that the graph is connected.

Vertices are numbered from 1 to n.

outputFormat

Output a single integer — the minimum total weight of a spanning tree containing exactly need white edges.

sample

4 5 2
1 2 1 W
2 3 2 B
3 4 3 W
4 1 4 B
2 4 5 W

6