MST (Meaningless State Team) компани нь Берландийн бас нэгэн улсын чухал тендерт
ялжээ.
Берланд $n$ ширхэг хоттой бөгөөд зарим хотууд нь хоорондоо замаар холбогдсон
байдаг. Зам бүр нь хоёр урсгалтай бөгөөд бүгд өөрийн гэсэн төлбөртэй. MST багийн
үүрэг бол аль ч хоёр хотын хооронд тэдний зассан замаар очиж болдог байх мөн
хотын төвтэй $k$ зам холбогдсон байхаар замуудыг засах юм. Хотын төв нь $1$-дэх
хот юм.
MST багийнханд тусалж хамгийн бага зардлаар дараах засварыг хэдээр гүйцэтгэж
болохыг хэлж өгнө үү?
Эхний мөрөнд нийт хотын тоо $n$, замуудын тоо $m$ болон $k$
($1 ≤ n ≤ 5000;0 ≤ m ≤ 10^5;0 ≤ k < 5000$) тоонууд өгөгдөнө. Дараагийн $m$
мөрөнд $a_i$ болон $b_i$ хотуудыг холбосон $w_i$ төлбөртэй гүүр байгаа гэдгийг
илтгэх $3$ тоонууд өгөгдөнө. ($1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 10^5$)
Эхний мөрөнд засах замуудын нийт тоог харин дараагийн мөрөнд засах замуудын
дугааруудыг хэвлэнэ. Хэрэв нөхцөлийг хангах замууд олдохгүй бол $-1$-ийг
хэвлэнэ.
-- Энхсанаа