Description

Original source: 2012 National Training Team Mutual Testing

You are given an undirected, weighted, connected graph where each edge is either black or white. Your task is to find a minimum-weight spanning tree that contains exactly need white edges. The problem guarantees a solution exists.

Input Format

The first line contains V, E, and need, representing the number of vertices, edges, and the required number of white edges, respectively.

Each of the next E lines contains s, t, c, and col, representing the endpoints of the edge (vertices are labeled starting from 0), the edge weight, and the color (0 for white, 1 for black).

Output Format

A single line representing the total weight of the edges in the desired spanning tree.

Sample 1

2 2 1
0 1 1 1
0 1 2 0

2

Data Range and Hints

For all data, V ≤ 5×10^4, E ≤ 10^5, and edge weights are positive integers in the range [1, 100].