Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Poltu and Minimum Spanning Tree

By RamprosadG · Limits 5s, 512 MB

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

Input

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.

Output

Print the cost of minimum spanning tree, if there is a valid solution. Otherwise, print -1.

Samples

InputOutput
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
InputOutput
3 3 1
1 2 6 1
1 3 5 1
2 3 4 1

-1

    Discussion

    Statistics


    33% Solution Ratio

    YouKnowWhoEarliest, 2w ago

    RAKIBULHOSSAINFastest, 1.3s

    RAKIBULHOSSAINLightest, 14 MB

    RAKIBULHOSSAINShortest, 1736B

    Submit

    Login to submit