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.

Input

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.

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, 4M ago

RAKIBULHOSSAINFastest, 1.3s

RAKIBULHOSSAINLightest, 14 MB

RAKIBULHOSSAINShortest, 1736B

Submit

Login to submit