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$-ийг хэвлэнэ.