Boltu gave a simple task to his best friend Poltu. You are a good programmer. So, Poltu hired you to solve the given task.
This task is so simple and described below:
You are given an bidirectional weighted graph with $N$
nodes and $M$
edges. Every edge is colored with black or white color (0 means black and 1 means white). You are given also an integer $K$
. You have to find the minimum spanning tree such that there is exactly K white edges in the tree or identify there is no solution.
The graph is connected and there can be multiple edges between two nodes.
First line contains three integers $N$
, $M$
and $K$
($1 ≤ N ≤ 200000$
, $N - 1 ≤ M ≤ 500000$
, $0 ≤ K ≤ N - 1$
)
The next $M$
lines contains four integers $u$
, $v$
($1 ≤ u, v ≤ N$
), $w$
($1 ≤ w ≤ 1000000000$
) and $c$
($0 ≤ c ≤ 1$
), an edge between $u$
and $v$
whose weight is $w$
and color is $c$
.
It is guaranteed that, the given input makes a connected graph.
Print the cost of minimum spanning tree, if there is a valid solution. Otherwise, print -1.
Input | Output |
---|---|
4 6 2 1 2 3 1 1 4 2 0 1 3 12 1 2 4 10 0 2 3 4 0 3 4 7 1 | 12 |
Input | Output |
---|---|
3 3 1 1 2 6 1 1 3 5 1 2 3 4 1 | -1 |