Yemək Rəyi
Frida, Cosmopolitan üçün restoran rəyləri yazan bir yazıçıdır. O, bu işdən çox zövq alır, lakin illər ərzində demək olar ki, bütün restoranları nəzərdən keçirdiyini düşünür. İndi isə yeni bir mərhələyə keçmək vaxtıdır; o, oxucuların hansı uçuşları seçmələri barədə daha yaxşı qərar vermələrinə kömək etmək üçün hava yolları tərəfindən təqdim olunan yeməkləri nəzərdən keçirəcək.
Rəhbəri ona Cosmopolitan-ın növbəti buraxılışı üçün nəzərdən keçirməli olduğu uçuşların siyahısını təqdim edib. Frida bilir ki, hər uçuşda hər iki istiqamətdə eyni yemək təqdim olunur, buna görə də hər uçuşu yalnız bir dəfə nəzərdən keçirməlidir. O, başa düşür ki, bəzi əlavə uçuşlar etməli olacaq, çünki rəhbərinin siyahısındakı uçuşlarla bütün rəyləri tamamlaya bilmir. Buna görə də, o, tez bir araşdırma apararaq əlavə uçuşların siyahısını hazırlayıb. Bu uçuşlarda yeməkləri nəzərdən keçirməyəcək; onlar yalnız bütün rəyləri tamamlamaq üçün istifadə olunacaq. Fridanın məqsədi, uçuş biletlərinə ən az pul xərcləyərək bütün rəyləri tamamlamaqdır. Onun ofisi Stokholmda yerləşir, buna görə də səyahətinə oradan başlayır və orada bitirir. Hər uçuş iki şəhər arasında hər iki istiqamətdədir və hər iki istiqamətdə sabit qiymətə malikdir. Bütün rəyləri bəzi əlavə uçuşlardan istifadə edərək tamamlamağın mümkün olduğunu güman edə bilərsiniz.
Bu problemin məqsədləri üçün Fridanın yaşayış üçün ödəməli olduğu qiyməti və uçuşların gediş və gəliş vaxtlarını nəzərə almırıq, çünki hər uçuşun çox tez-tez və kifayət qədər qısa olduğunu güman edirik. Biz yalnız uçuşların ümumi qiymətinə diqqət yetiririk.
Giriş verilənləri
Girişdə bir neçə test halı olacaq.
Hər test halı 2 boşluqla ayrılmış tam ədədlə N, R, (2 ≤ N ≤ 13, 0 ≤ R ≤ 78) başlayan bir sətirdən ibarət olacaq, burada N girişdə qeyd olunan hava limanlarının sayı və R nəzərdən keçirilməli olan uçuşların sayıdır. Hava limanları 1, ..., N ilə nömrələnib və Stokholm 1 nömrəsinə malikdir.
Növbəti R sətir R nəzərdən keçirilməli olan uçuşları təsvir edir. Hər sətir 3 boşluqla ayrılmış tam ədəd a, b, c (1 ≤ a, b ≤ N, 1 ≤ c ≤ 10000) ehtiva edir, burada a, b 2 fərqli hava limanını göstərir və c hər iki istiqamətdə uçuşun İsveç kronunda qiymətidir. Heç bir 2 şəhər cütü iki dəfə siyahıya alınmayıb.
Növbəti sətir F tam ədədini ehtiva edir, (0 ≤ F ≤ 200), mövcud olan əlavə uçuşların sayını göstərir.
Növbəti F sətir eyni formatda uçuş təsvirlərini ehtiva edir və bir şəhər cütü arasında daha çox uçuş ola bilər. Bütün rəyləri bəzi əlavə uçuşlardan istifadə edərək tamamlamağın mümkün olduğunu güman edə bilərsiniz.
Giriş "0 0" sətiri ilə bitəcək.
Çıxış verilənləri
Hər test halı üçün Fridanın bütün rəyləri edə bilməsi və Stokholma qayıda bilməsi üçün uçuş biletlərinin ən aşağı ümumi qiymətini göstərən bir tam ədəd çıxarın.