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.

If you do not know about minimum spanning tree see this

First line contains three integers N, M and K. (1 ≤ N ≤ 200000, N - 1 ≤ M ≤ 500000 and 0 ≤ K ≤ N - 1)
The next M lines contains four integers u, v, w and c, an edge between u and v whose weight is w and color is c. (1 ≤ u, v ≤ N, 1 ≤ w ≤ 1000000000, 0 ≤ c ≤ 1)

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.