Rəqib - şəhərlər
Flatlandiya ölkəsində N şəhər var, hər şəhər satış üçün M sayda maldan müəyyən birini satışa çıxardır. Eyni malı satışa çıxardan şəhərlər rəqib şəhərlərdir. Flatlandiyanın şəhərləri bir ticarət şəbəkəsində birləşmək istəyirlər. Tədqiqatlar göstərir ki, hər hansı bir şəhərin ticarət şəbəkəsinə birləşə bilməsi üçün istənilən A şəhərindən şəbəkə yolu ilə istənilən digər B şəhərinə çata bilmək zəruri və kafidir. Həm də nəzərə almaq lazımdır ki, belə şəbəkədə rəqib-şəhərlər arasında yol olmamalıdır, başqa sözlə, rəqib-şəhərlər bu şəbəkədə qonşu deyildirlər.
Sizin tapşırıq - Flatlandiyanın verilmiş şəhərinə görə yol şəbəkəsini elə qurmalı ki, şəbəkənin uzunluğu minimum olsun. Şəbəkənin uzunluğu çəkilmiş yolların uzunluqları cəmidir. Şəhərlər arasında yollar elə çəkilməlidir ki, onlara yalnız onları birləşdirən şəhərlərdən gəlmək mümkün olsun. Kəsişmələrdən qaçmaq üçün yolları müxtəlif səviyyələrdə yerləşdirmək olar.
Giriş verilənləri
Giriş faylının birinci sətrində aralarında boşluq işarəsi olmaqla iki tam N və M (1 ≤ N ≤ 200, 1≤ M ≤ 200) ədədləri yazılır. Sonrakı N sətirdə hər bir şəhər bir sətirdə olmaqla Flatlandiya şəhərləri təsvir edilir. Uyğun sətirdə aralarında boşluq işarəsi olmaqla üç ram X_i, Y_i,Z_i, ədədi yazılır. Burada X_i və Y_i i-ci şəhərin koordinatları, Z_i isə bu şəhərin satışa çıxardığı malın nömrəsidir (-10000 ≤ X_i, Y_i ≤ 10000, 1 ≤ Z_i ≤ M, 1 ≤ i ≤ N).
Çıxış verilənləri
Çıxış faylının birinci sətrində 0.001 dəqiqliklə bir həqiqi ədəd-yol şəbəkəsinin minimum uzunluğu verilir. Əgər şəhəri ticarət şəbəkəsi ilə birləşdirmək mümkün deyilsə, çıxışa -1 verin.