Bileti Al və Get
Ticket to Ride, 5 oyunçuya qədər oynana bilən bir stolüstü oyundur. Oyunun məqsədi qatar xətləri qurmaq və rəqiblərin qatar xətləri qurmaq cəhdlərini pozmaqdır. Oyunun əvvəlində hər bir oyunçuya dörd qatar xətti tapşırığı verilir. Oyunçu bu dörd tapşırıqdan istədiyi qədərini ləğv edə bilər. Hər bir tapşırığın çətinliyinə uyğun bir xal dəyəri var (məsələn, Stokholm və Tokio arasında bir qatar xətti, Stokholm və Utrext arasında bir qatar xəttindən daha çox xal dəyərinə malik ola bilər). Oyunun sonunda hər bir oyunçu uğurla tamamladığı tapşırıqlar üçün xal qazanır və tamamlamadığı tapşırıqlar üçün cəza xalları alır.
Bir tapşırıq, bir sıra qısa dəmir yolu marşrutları ilə birləşdirilməli olan şəhər cütündən ibarətdir. Bir marşrut müəyyən bir xərc qarşılığında iddia edilə bilər, lakin işlər mürəkkəbləşir, çünki məhdud sayda marşrut var və bir oyunçu marşrutu iddia etdikdən sonra digər oyunçular onu iddia edə bilməz. Bir oyunçu iki şəhər arasında qatar xəttini uğurla qurubsa, bu oyunçu tərəfindən iddia edilən marşrutlardan istifadə edərək iki şəhər arasında bir yol varsa, bu xətt qurulmuş sayılır. Sadəlik üçün oyunun bütün əlavə aspektlərini (marşrutların iddia edilməsi prosesi və əlavə xal qazanma yolları daxil olmaqla) nəzərə almayacağıq.
Məsələn, əgər tapşırığınız yuxarıdakı şəkildə Stokholm və Amsterdamı birləşdirməkdirsə, yəqin ki, Stokholm və Kopenhagen, həmçinin Kopenhagen və Amsterdam arasındakı marşrutları iddia etmək istəyəcəksiniz. Lakin başqa bir oyunçu Kopenhagen və Stokholm arasındakı marşrutu sizdən əvvəl iddia edərsə, qatar xəttiniz Kopenhagendən Oslodan keçərək digər marşrutlardan istifadə etməlidir.
Bu məsələdə, dörd tapşırığın hamısını yerinə yetirməyə çalışmaq kimi cəsarətli bir strategiyanı nəzərdən keçirəcəyik (adətən bu, çox çətin olacaq). Buna nail olmağın çətinliyini ilkin qiymətləndirmək üçün, digər oyunçuların planlarımıza müdaxilə etmədiyini nəzərə alaraq, bütün dörd xətti qurmağın minimum xərcini hesablamaq istəyirik. Sizin işiniz bu minimum xərci müəyyən etmək üçün bir proqram yazmaqdır.
Giriş verilənləri
Giriş, təhlil ediləcək bir neçə (ən çox 20) oyundan ibarətdir. Hər oyun, xəritədəki şəhərlərin və dəmir yolu marşrutlarının sayını verən iki tam ədəd 1 ≤ n ≤ 30, 0 ≤ m ≤ 1000 ilə başlayır. Sonra n sətir gəlir, n şəhərin adlarını verir. Şəhər adları ən çox 20 simvoldan ibarətdir və yalnız kiçik hərflərdən ('a'-'z') ibarətdir.
Bundan sonra m sətir gəlir, hər biri iki fərqli şəhərin adını və 1 ≤ c ≤ 10000 tam ədədini ehtiva edir, bu da həmin iki şəhər arasında xərc c olan bir dəmir yolu marşrutunun olduğunu göstərir. Eyni şəhər cütü arasında bir neçə dəmir yolu marşrutu ola bilər. Hər hansı bir şəhərdən digər şəhərə qatar xətti qurmağın həmişə mümkün olduğunu qəbul edə bilərsiniz.
Nəhayət, dörd sətir olacaq, hər biri iki şəhərin adını ehtiva edəcək, dörd qatar xətti tapşırığını verəcək.
Giriş n = m = 0 olan bir hal ilə tamamlanır. Bu hal işlənməməlidir.
Çıxış verilənləri
Hər oyun üçün, bütün dörd qatar xəttini qurmağın mümkün olan minimum xərcini ehtiva edən tək bir sətir çıxarın.