Poltu and Minimum Spanning Tree

RamprosadG Replay of BSMRSTU Home Qu...
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 NN nodes and MM edges. Every edge is colored with black or white color (0 means black and 1 means white). You are given also an integer KK. 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.

Input

First line contains three integers NN, MM and KK (1N2000001 ≤ N ≤ 200000, N1M500000N - 1 ≤ M ≤ 500000, 0KN10 ≤ K ≤ N - 1)

The next MM lines contains four integers uu, vv (1u,vN1 ≤ u, v ≤ N), ww (1w10000000001 ≤ w ≤ 1000000000) and cc (0c10 ≤ c ≤ 1), an edge between uu and vv whose weight is ww and color is cc.

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

Submit

Login to submit.

Statistics

39% Solution Ratio
YouKnowWhoEarliest, May '20
steinumFastest, 1.0s
steinumLightest, 9.7 MB
steinumShortest, 1554B
Toph uses cookies. By continuing you agree to our Cookie Policy.