Cənubi Butovonun əfsanələri və mifləri#4161
3141-ci ildə Butovo bölgəsi qeyri-adi bir problemlə üz-üzə qaldı: təhlükəli deyil, lakin qəribə bir sınaq! Şıltaq robot göyərçinlər şəhərin meydanlarına baş çəkiblər! Onlar küçə kəsişmələrində istiqamətini dəyişmək istəyən hər kəsi zarafatla çaşdırır, bu isə sakinlərin hərəkətini xeyli çətinləşdirir.
Butovo şimal-cənub prospektləri və şərq-qərb küçələri ilə təşkil olunub. Hər prospekt hər küçə ilə dəqiq bir kəsişmədə kəsişir. Prospekt və ya küçə boyunca düz hərəkət etmək asandır, amma hər hansı kəsişmədə dönmək əsl macəradır — çünki məhz orada robot göyərçinlər yığışırlar.
Şəhər sakinlərinin rahat hərəkəti üçün bələdiyyə müəyyən kəsişmələrdə xüsusi bələdçi kabinələri qurmaq qərarına gəlib. Bu kabinələrdə mehriban bələdçilər hər kəsi təhlükəsiz və şən formada istiqamətləndirə bilirlər və beləliklə insanlar bu kabinələr qoyulan kəsişmələrdə rahatlıqla istiqamətini dəyişə bilərlər.
Lakin builki büdcə məhduddur, çünki mer böyük bir şəhər bağı layihəsinə vəsait yönəldib. Odur ki, məqsəd mümkün qədər az sayda kabinə və minimum ümumi xərclə bu planı həyata keçirməkdir. Hər şey düzgün işləsin deyə, kabinələr elə yerləşdirilməlidir ki, hər kəsişmədən istənilən digər kəsişməyə yalnız bu xüsusi kabinələrin olduğu yerlərdə dönməklə çatmaq mümkün olsun.
Burada problem bitmir: Butovonun fərqli hissələrində kabinə tikinti xərcləri də fərqlidir. Hər sahənin mərkəzi müəyyən bir kəsişmədə yerləşir və istənilən digər kəsişmə, ona ən yaxın sahənin mərkəzinə qədər olan məsafəyə görə həmin sahəyə məxsusdur. Bu məsafə isə belə hesablanır: bir kəsişmədən digərinə getmək üçün tələb olunan minimum aralıq kəsişmələrin sayı üstəgəl bir. Əgər bir neçə sahənin mərkəzinə qədər məsafə bərabər olarsa, robot göyərçinlərin davamlı yığıncaqları orada kabinə qurmağa imkan vermir.
Sizdən tələb olunan: Butovonun xəritəsi verilməklə, minimum sayda və minimum ümumi xərclə bələdçi kabinələrinin quraşdırıldığı yerlərin tapılmasıdır ki, beləliklə hər iki kəsişmə arasında yalnız bu kabinələrdə döncə edilə və istənilən yerə çatmaq mümkün olsun.
Birinci sətrdə , və — Butovoda prospektlərin, küçələrin və sahələrin sayı verilir (2 \leq N, M \leq 500, 1 \leq R \leq 1000). Sonra sətrin hər birində üç tam ədəd verilir: sahənin mərkəzinin prospekt və küçə nömrəsi və həmin sahədə kabinə tikinti xərci. Prospektlər və küçələr birindən başlayır. Bütün tikinti xərcləri müsbət və minə qədərdir. Heç bir iki sahənin mərkəzləri üst-üstə düşmür.
Cavabın birinci sətrində iki tam ədəd olmalıdır: kabinələrin yerləşdirildiyi kəsişmələrin sayı və minimum ümumi tikinti xərci. Növbəti sətrdə isə hər kabinənin yerləşdiyi kəsişmənin prospekt və küçə nömrəsi göstərilməlidir. Əgər tapşırığın tələblərinə uyğun kabinələr yerləşdirmək mümkün deyilsə, yalnız -1 çap edin.
Nümunə 1