Дві Відомі Компанії

У Китаї є дві компанії, які надають Інтернет-послуги для всіх міст: 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.