Poltu and Minimum Spanning Tree

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

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