Cənubi Butovonun əfsanələri və mifləri
У 3141 ilində Butovo çox təhlükəli bir məhəlləyə çevrildi, qatil və digər cinayətkarlarla dolu. O qədər təhlükəli ki, hətta tankla hərəkət etmək qorxulu oldu!
Xatırladaq ki, Butovo N prospektdən ibarətdir, şimaldan cənuba doğru gedir, və M küçədən ibarətdir, şərqdən qərbə doğru gedir. Hər bir prospekt hər bir küçə ilə dəqiq bir kəsişmədə kəsişir. Prospekt və ya küçə boyunca yüksək sürətlə hərəkət etmək təhlükəsizdir, amma hər hansı bir yerdə dönmək əksinə, çox təhlükəlidir, çünki bunun üçün sürəti azaltmaq lazımdır və bu anda yerli sakinlərin dəstələri sizə hücum etməyə başlayır.
Butovo Polis İdarəsi vəziyyəti bir az düzəltməyə qərar verdi. İdarə rəhbərləri qərara gəldilər ki, bəzi kəsişmələrdə bir neçə post yerləşdirmək olar ki, sakinlər orada sakitcə dönə bilsinlər, hücuma məruz qalmaqdan qorxmadan, çünki polis artıq ən yeni "Muşket-1812" tüfənglərini silahlanmaya götürüb və hər hansı bir şey baş verərsə, hər bir qanunabiding vətəndaşın şərəf və ləyaqətini qoruya biləcək.
Təəssüf ki, məhz bu il idarə rəisi özünə yeni elit malikanə tikməyə qərar verdi, buna görə də idarə mümkün qədər az pul xərcləməyə qərar verdi yeni postların tikintisinə. Lakin, hər şeyin təmiz görünməsi üçün postları elə tikmək lazımdır ki, istənilən kəsişmədən digərinə təhlükəsiz şəkildə çatmaq mümkün olsun, yalnız xüsusi təchiz olunmuş postlarda dönərək. Əks halda yoxlama gələcək və hamını işdən çıxaracaqlar.
Butovonun problemləri bununla bitmədi. Butovonun bəzi bölgələri daha təhlükəlidir və daha təhlükəli bölgələrdə tikiləcək postlar daha bahalıdır. Hər bir bölgənin mərkəzi var, hansı ki, müəyyən bir kəsişmənin yaxınlığında yerləşir. İstənilən digər kəsişmə, mərkəzi kəsişməyə ən yaxın olan bölgəyə aiddir. Kəsişmələr arasındakı məsafə, Butovo məsafəsi adlanan üsulla ölçülür: iki kəsişmə arasındakı məsafə, bir bölgədən digərinə keçmək üçün lazım olan minimum aralıq kəsişmələrin sayı, üstəgəl bir. Əgər müəyyən bir kəsişməyə minimal məsafədə olan bir neçə bölgə mərkəzi varsa, o kəsişmədə iki nüfuzlu şəxsin daimi qarşıdurmaları baş verir, buna görə də o kəsişmədə post tikmək mümkün deyil.
Sizə Butovonun bölgələrinin yerləşməsini bilmək lazımdır ki, istənilən kəsişmədən digərinə təhlükəsiz çatmaq üçün postların tikintisinin minimal dəyərini müəyyən edəsiniz.
Giriş verilənləri
Giriş faylının ilk sətiri Butovodakı prospektlərin sayı N, küçələrin sayı M və bölgələrin sayı R olan üç rəqəmi ehtiva edir (2 ≤ N, M ≤ 500, 1 ≤ R ≤ 1000). Növbəti R sətir hər biri üç tam rəqəm ehtiva edir - müvafiq bölgənin mərkəzinin yerləşdiyi prospekt və küçənin nömrəsi və bu bölgədə post tikintisinin dəyəri. Prospektlər və küçələr birdən nömrələnir, tikinti dəyəri hər yerdə müsbətdir və minə qədərdir. Heç bir iki bölgə eyni mərkəzə malik deyil.
Çıxış verilənləri
Çıxış faylının ilk sətirində iki rəqəm çıxarın: postların tikilməli olduğu kəsişmələrin sayı K və tapılmış minimal ümumi tikinti dəyəri. Növbəti K sətir tapılmış kəsişmələrin təsvirlərini ehtiva etməlidir: müvafiq kəsişmənin yerləşdiyi prospekt və küçənin nömrəsi. Əgər postları lazım olduğu kimi yerləşdirmək mümkün deyilsə, çıxış faylına yalnız -1 rəqəmi çıxarın.