Телепорт
Teymur kainatı araşdırmağa qərar verdi. Onun bəxtinə kainat çox kiçik idi və n planetdən ibarət idi. Teymurun dövründə planetlər arasında səyahət üçün k paralel kainat istifadə olunurdu. Bunun üçün bəzi planet cütləri arasında iki tərəfli portallar mövcud idi. Hər planetdə hər paralel kainat üçün ən çox bir portal var idi. Planetlər arasında keçid ani baş verirdi və heç bir xərc tələb etmirdi: səyyah i-ci kainatın portalına a planetində daxil olur, i-ci kainatın portalından b planetində çıxır və bir aspirin həbi içirdi (hətta paralel kainatda ani qalmaq belə, "Bax effekt" adlanan səbəbdən dözülməz baş ağrısına səbəb olurdu). Bir planetdəki portallar arasında köhnə və etibarlı üsulla - foton dirijablları ilə hərəkət etmək lazım idi. Belə bir dirijabl üçün biletin qiyməti hər planet və onun üzərindəki portal cütləri üçün fərqli idi.
Teymur 1 planetinin 1 portalının yaxınlığında yaşayır. O, k planetinin n portalına çatmalıdır, burada onu komandası gözləyir. Bu səyahəti həyata keçirmək üçün o, özü ilə minimum neçə aspirin həbi və nə qədər pul götürməlidir? Teymur üçün sağlamlıq maddi zənginlikdən daha vacibdir, buna görə də o, daha az aspirin içməyi üstün tutur, hətta daha çox pul xərcləməli olsa belə.
Giriş verilənləri
Birinci sətir 3 tam ədədi ehtiva edir: kainatda olan planetlərin sayı n, planetlər arasında olan portalların sayı m və paralel kainatların sayı k (1 ≤ n ≤ 100, 1 ≤ k ≤ 11, 1 ≤ m ≤ 100000). Növbəti m sətirin hər biri 3 tam ədəd a, b, c ehtiva edir - planetlərarası portalın təsviri: a, b - portal ilə birləşdirilən planetlər (1 ≤ a, b ≤ n), c - portal tərəfindən istifadə olunan paralel kainatın nömrəsi (1 ≤ c ≤ k). Daha sonra hər biri k sətirdən ibarət n blok gəlir, hər biri k tam ədəd ehtiva edir - hər planetdəki foton dirijabllarının marşrutlarının təsviri. i-ci blokun j-ci sətirinin k-ci elementi i planetində j portalından k portalına dirijabl biletinin tenge ilə qiymətidir. Qiymətlər 1 ilə 100 arasında tam ədədlərdir. Sətirlərdəki ədədlər boşluqlarla ayrılır.
Çıxış verilənləri
Boşluqla ayrılmış iki tam ədəd: minimum aspirin həbi sayı və bununla mümkün olan minimum tenge məbləği.