Qida məhsullarının icmalı

Frida Cosmopolitan-da işləyir və restoranların icmallarını yazır. O, işini sevir, lakin illər ərzində Yer üzündəki bütün restoranları nəzərdən keçirdiyini düşünür. İndi bir səviyyə yuxarı keçmək vaxtıdır; o, aviaşirkətlər tərəfindən təqdim olunan yeməklərin icmalını yazmağı planlaşdırır ki, oxucular uçuşları haqqında daha əsaslı qərarlar qəbul edə bilsinlər.

Fridanın müdiri ona Cosmopolitan-ın növbəti buraxılışında nəzərdən keçirməli olduğu uçuşların siyahısını verdi. O bilir ki, hər bir uçuşun hər iki istiqamətində eyni yemək təqdim olunur, buna görə də hər bir reysi yalnız bir dəfə yoxlamaq kifayətdir. O, həmçinin başa düşdü ki, yalnız müdirinin siyahısındakı reyslərdən istifadə edərək bütün icmalları edə bilməyəcəyi üçün bəzi əlavə reyslərdən də istifadə etməlidir. Buna görə də o, bir neçə sürətli araşdırma apardı və istifadə edə biləcəyi əlavə reyslərin siyahısını tərtib etdi. Frida bu reyslərdəki yeməkləri öyrənməyəcək; onlar yalnız tələb olunan bütün icmalları edə bilməsi üçün istifadə olunacaq.

Fridanın məqsədi təyyarə biletlərinə minimum pul xərcləyərək bütün icmalları etməkdir. Onun ofisi Stokholmda yerləşir, ona görə də o, səyahətə məhz oradan başlayır və orada bitirir. İki şəhər arasında hər bir uçuşun hər iki istiqamətdə sabit qiyməti var. Bəzi əlavə reyslərdən istifadə edərək bütün icmalları yazmaq mümkün olduğu məlumdur.

Bu məsələdə Fridanın yaşayış üçün ödəməli olduğu qiyməti, eləcə də uçuşların uçuş və eniş vaxtını nəzərə almayacağıq, çünki uçuşların kifayət qədər tez-tez və qısa müddətdə həyata keçirildiyini düşünürük. Biz yalnız uçuşların ümumi dəyərinin minimallaşdırılması ilə maraqlanırıq.

Giriş məlumatları

Birinci sətir n və r (2 ≤ n ≤ 13, 0 ≤ r ≤ 78) tam ədədlərini ehtiva edir, burada n - hava limanlarının sayı və r - icmallar yazılmalı olan uçuşların sayı. Hava limanları 1, ..., n nömrələri ilə nömrələnmişdir, Stokholm 1 nömrəsinə malikdir.

Növbəti r sətir r nəzərdən keçirilməli olan reysləri təsvir edir. Hər bir sətir 3 ədəd a, b, c (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10000) ehtiva edir, burada a və b iki fərqli hava limanını təyin edir və c - hər iki istiqamətdə uçuşun İsveç kronunda qiymətidir. İki şəhərdən ibarət heç bir cüt iki dəfə təqdim olunmur.

Növbəti sətir icazə verilən əlavə reyslərin sayı f (0 ≤ f ≤ 200) ehtiva edir. Növbəti f sətir əlavə reysləri əsas reyslər kimi eyni formatda təsvir edir. Bir şəhər cütü arasında bir neçə reys mövcud ola bilər. Bəzi əlavə reyslərdən istifadə edərək bütün icmalları yazmağın mümkün olduğunu düşünün.

Çıxış məlumatları

Fridanın bütün icmalları etmək və Stokholma geri qayıtmaq üçün ödəməli olduğu biletlərin ən kiçik ümumi dəyərini çıxış edin.