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 nodes and edges. Every edge is colored with black or white color (0 means black and 1 means white). You are given also an integer . 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 , and (, , )
The next lines contains four integers , (), () and (), an edge between and whose weight is and color is .
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 |