Две Известные Компании

В Китае есть две компании, предоставляющие интернет-услуги для всех городов: China Telecom и China Unicom. Обе компании планируют проложить кабели между городами. Правительство, естественно, хочет соединить все города с минимальными затратами. Поэтому министр финансов, г-н Б, должен выбрать некоторые из предложенных планов прокладки кабелей от обеих компаний и определить минимальную стоимость, необходимую для соединения всех городов. Г-н Б знает, что для соединения всех N городов Китая необходимо построить N-1 кабелей. По определённым причинам г-н Б обязан выбрать K кабелей от China Telecom, а остальные N-1-K кабелей от China Unicom. Ваша задача — помочь г-ну Б определить, какие кабели следует построить и какова минимальная стоимость их строительства. Вы можете быть уверены, что решение всегда существует.

Входные данные

Каждый тестовый случай начинается с строки, содержащей количество городов N (1 ≤ N ≤ 50000), количество планов прокладки кабелей M (N-1 ≤ M ≤ 100000) и количество требуемых кабелей от China Telecom K (0 ≤ K ≤ N-1). Далее следуют M строк, каждая из которых содержит четыре целых числа a, b, c, x (0 ≤ a, b ≤ N-1, a != b, 1 ≤ c ≤ 100, x в {0, 1}), указывающие пару городов, которые соединит этот кабель, стоимость его строительства и компанию, которой принадлежит этот план прокладки кабеля. x=0 обозначает, что план прокладки кабеля принадлежит China Telecom, а x=1 обозначает, что план прокладки кабеля принадлежит China Unicom.

Выходные данные

Для каждого тестового случая выведите номер случая и минимальную стоимость строительства кабелей.

Примеры

Примечание

В первом случае есть два плана прокладки кабелей между двумя городами, один от China Telecom и один от China Unicom. Г-н Б должен выбрать тот, который от China Telecom, чтобы удовлетворить требованиям задачи, даже если стоимость выше.

Во втором случае г-н Б должен выбрать кабель от China Unicom, что приводит к ответу 1.