Dünya Səyahəti#3293
Kita_masa dünya ətrafında bir səyahət planlaşdırır. Bu dünyada N ölkə var və hər bir i-ci ölkədə M_i şəhər mövcuddur. Kita_masa hər şəhəri yalnız bir dəfə ziyarət edib başladığı şəhərə geri dönmək istəyir.
Bu dünyada insanlar yalnız təyyarə ilə səyahət edə bilərlər. İki növ hava yolları mövcuddur: daxili və beynəlxalq xətlər. Beynəlxalq hava limanları xüsusi obyektlər, məsələn, gömrük və pasport nəzarəti tələb etdiyindən, hər ölkədə yalnız bir neçə şəhərdə beynəlxalq hava limanları yerləşir.
Sizə bu dünyadakı bütün uçuş marşrutlarının siyahısı və hər bir marşrutun qiymətləri təqdim olunur. İndi Kita_masa'nın dünya səyahəti üçün ən ucuz marşrutu tapmaq vaxtıdır!
Birinci sətirdə iki tam ədəd N və K verilir, burada N ölkələrin, K isə uçuş marşrutlarının sayını göstərir. İkinci sətirdə N tam ədəd verilir, burada i-ci ədəd i-ci ölkədəki şəhərlərin sayını göstərir. Üçüncü sətirdə də N tam ədəd verilir, burada i-ci ədəd i-ci ölkədəki beynəlxalq hava limanlarının sayını göstərir. Sonrakı K sətir beş tam ədəd [Ölkə 1] [Şəhər 1] [Ölkə 2] [Şəhər 2] [Qiymət] ehtiva edir. Bu, [Ölkə 1]-dəki [Şəhər 1] ilə [Ölkə 2]-dəki [Şəhər 2] arasında iki tərəfli uçuş marşrutunun olduğunu və qiymətinin [Qiymət] olduğunu bildirir.
Qeyd edək ki, hər ölkədəki şəhərlər 1-dən başlayaraq nömrələnir və yalnız nömrəsi F_i-dən kiçik və ya bərabər olan şəhərlər beynəlxalq hava limanlarına malikdir. Yəni, əgər c_1 ölkəsindəki n_1 şəhəri ilə c_2 ölkəsindəki n_2 şəhəri arasında uçuş varsa, bu, n_1 ≤ F_c1 və n_2 ≤ F_c2 olmalıdır. Sizə bir şəhərdən çıxıb eyni şəhərə geri dönən uçuş marşrutunun olmadığını və hər şəhər cütü üçün yalnız bir uçuş marşrutunun mövcud olduğunu qəbul edə bilərsiniz.
Hər verilənlər dəsti üçün aşağıdakı məhdudiyyətlər mövcuddur:
1 ≤ N ≤ 15
1 ≤ M_i ≤ 15
1 ≤ F_i ≤ 4
sum(F_i) ≤ 15
1 ≤ Qiymət ≤ 10,000
Dünya səyahətini həyata keçirmək üçün minimum qiyməti təmsil edən bir sətir çap edin.
Əgər belə bir səyahət mümkün deyilsə, -1 çap edin.
Nümunə 1