İki Məşhur Şirkət

Çində, bütün şəhərlər üçün İnternet xidməti təklif edən iki şirkət var: China Telecom və China Unicom. Hər iki şirkət şəhərlər arasında kabellər çəkməyi planlaşdırır. Hökumət isə bütün şəhərləri ən az xərclə birləşdirmək istəyir. Buna görə də, maliyyə naziri cənab B, iki şirkətdən bəzi kabel planlarını seçərək bütün şəhərləri birləşdirmək üçün lazım olan minimum xərci hesablamaq istəyir. Cənab B bilir ki, Çinin bütün N şəhərini birləşdirmək üçün N-1 kabel çəkilməlidir. Bəzi xüsusi səbəblərə görə, cənab B China Telecom-dan K kabel seçməli və qalan N-1-K kabelləri China Unicom-dan seçməlidir. Sizin vəzifəniz cənab B-yə hansı kabellərin çəkilməli olduğunu və onları çəkmək üçün minimum xərci müəyyən etməkdə kömək etməkdir. Həllin həmişə mövcud olduğunu qəbul edə bilərsiniz.

Giriş verilənləri

Hər bir test halı şəhərlərin sayı N (1 ≤ N ≤ 50000), kabel planlarının sayı M (N-1 ≤ M ≤ 100000) və China Telecom-dan tələb olunan kabellərin sayı K (0 ≤ K ≤ N-1) olan bir sətirlə başlayır. Daha sonra M sətir gəlir, hər biri dörd tam ədəd a, b, c, x (0 ≤ a, b ≤ N-1, a != b, 1 ≤ c ≤ 100, x {0, 1}) ilə bu kabelin hansı şəhərləri birləşdirəcəyini, bu kabelin çəkilmə xərci və bu kabel planının hansı şirkətə aid olduğunu göstərir. x=0 kabel planının China Telecom-a aid olduğunu, x=1 isə China Unicom-dan olduğunu göstərir.

Çıxış verilənləri

Hər bir test halı üçün, halın nömrəsini və kabel çəkilişinin minimum xərci göstərin.

Nümunələr

Qeyd

Birinci halda, yalnız iki şəhər arasında iki kabel planı var, biri China Telecom-dan və biri China Unicom-dan. Cənab B problem tələblərinə uyğun olaraq China Telecom-dan olanı seçməlidir, hətta xərc daha yüksək olsa belə.

İkinci halda, cənab B China Unicom-dan olan kabeli seçməlidir, bu da cavabı 1 edir.