Gəlin axtarışında
Flatlandiya kralı bir gün k oğlunu gəlin axtarışına göndərməyə qərar verdi. Bildiyiniz kimi, Flatlandiyada n şəhər mövcuddur və bunlardan bəziləri yollarla bir-birinə bağlıdır. Kral paytaxtda, yəni 1 nömrəli şəhərdə yaşayır, n nömrəli şəhər isə gəlinləri ilə məşhurdur.
Kralın əmri belədir: oğullarının hər biri 1 nömrəli şəhərdən n nömrəli şəhərə yollarla getməlidir. Gəlinlərin çoxluğu ilə tanınan n şəhərində gözəl gəlinlərin sayı az olduğundan, oğullar bir-birindən çəkinirlər. Buna görə də, onlar elə bir yol seçməlidirlər ki, heç iki oğul eyni yoldan keçməsin (hətta fərqli vaxtlarda belə). Kral oğullarını sevdiyi üçün onların təyinat şəhərinə çatma müddətinin orta vaxtının minimal olmasını istəyir.
Giriş məlumatları
Birinci sətirdə n, m və k ədədləri (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ k ≤ 100) - Flatlandiyadakı şəhərlərin və yolların sayı, həmçinin kralın oğullarının sayı verilir. Sonrakı m sətirin hər biri üç tam müsbət ədəd ehtiva edir - müvafiq yolun birləşdirdiyi şəhərlər və onun keçilməsi üçün lazım olan vaxt (vaxt 10^6-dan çox deyil). Yollar hər iki istiqamətdə keçilə bilər və iki şəhər bir neçə yolla birləşdirilə bilər.
Çıxış məlumatları
Əgər kralın əmri yerinə yetirilə bilməzsə, birinci sətirdə -1 ədədini çıxarın. Əks halda, birinci sətirdə oğulların təyinat şəhərinə çatması üçün lazım olan minimal mümkün orta vaxtı (ondalık nöqtədən sonra 5 rəqəm dəqiqliyi ilə) çıxarın. Sonrakı k sətirdə oğulların yollarını çıxarın, əvvəlcə yoldakı yolların sayını və sonra yolların keçilməli olduğu ardıcıllıqla yolların nömrələrini çıxarın. Yollar girişdə verildiyi ardıcıllıqla birdən başlayaraq nömrələnir.