Həsr olunur
Gnomların böyüklərdən biri olmaq üçün qorxunc bir labirenti keçmələri lazımdır. Labirent o qədər dolaşıq və təhlükəlidir ki, gnomlar ora cüt-cüt buraxılmalıdır. Cütlük bir oğlan və bir qızdan ibarət olmalıdır. Oğlanların və qızların sayı fərqli olduğuna görə, kimlərsə labirenti bir neçə dəfə keçməli olacaq (əsas odur ki, hər bir gnom labirenti heç olmasa bir dəfə keçsin).
Hər bir oğlan-qız cütlüyü üçün, böyüklər bu cütlüyün labirentdən çıxış yolunu nə qədər vaxtda tapacağını bilirlər. Onlara bütün uşaqları labirentdən minimal mümkün vaxtda keçirməkdə kömək edin.
Giriş verilənləri
Giriş faylının ilk sətiri gnomların oğlanlarının və qızlarının sayını göstərən iki tam ədəd n və m (1 ≤ n, m ≤ 100), ikinci sətir isə birlikdə buraxıla biləcək cütlərin sayını göstərən r ədədini (1 ≤ r ≤ 1000) ehtiva edir. Növbəti r sətir hər biri üç ədəd ehtiva edir: a_i, b_i və c_i. Bu ədədlər a_i nömrəli oğlanın b_i nömrəli qızla labirentə gedə biləcəyini və onların orada birlikdə c_i saniyə qalacağını göstərir (1 ≤ c_i ≤ 1000). Hər bir gnomun labirentə gedə biləcəyi bir dostu olduğu təmin edilir.
Çıxış verilənləri
Çıxış faylının ilk sətirində keçidi minimal vaxtda həyata keçirmək üçün lazım olan vaxtı göstərin. İkinci sətirdə labirentə buraxılmalı olan cütlərin sayını k göstərin. Üçüncü sətir k tam ədəd ehtiva etməlidir - giriş faylında göstərildiyi kimi bu cütlərin nömrələri.