Avtobus Turu#3389
Varsavada turist olduğunuzu və şəhərdən kənarda yerləşən möhtəşəm bir cazibədar yeri görmək üçün avtobus turu sifariş etdiyinizi təsəvvür edin. Avtobus əvvəlcə şəhər ətrafında bir müddət (Varsava böyük bir şəhər olduğundan uzun müddət) hərəkət edir və müvafiq otellərdə insanları götürür. Sonra möhtəşəm cazibədar yerə gedir və bir neçə saatdan sonra şəhərə qayıdır, bu dəfə insanları düşürmək üçün hər otelə gedir.
Nədənsə, bunu etdiyiniz hər dəfə oteliniz həmişə götürülmək üçün ilk, düşürülmək üçün isə sonuncu ziyarət edilən olur, yəni bütün yerli otellərin iki o qədər də möhtəşəm olmayan görməli yerlər turuna dözməli olursunuz. Bu, açıq-aydın etmək istədiyiniz bir şey deyil (nədənsə həqiqətən otellərə marağınız yoxdursa), buna görə də bunu düzəldək. Biz görməli yerlər şirkətinə avtobus turlarını daha ədalətli marşrutlaşdırmağa imkan verəcək bir proqram hazırlayacağıq - bu, bəzən hər kəs üçün daha uzun ümumi məsafə demək ola bilər, amma ədalət ədalətdir, elə deyilmi?
Bu problem üçün başlanğıc yeri (görməli yerlər şirkətinin qərargahı), götürmə və düşürmə üçün ziyarət edilməli olan h otel və təyinat yeri (möhtəşəm cazibədar yer) var. Biz qərargahdan başlayaraq, bütün otellərdən keçərək cazibədar yerə, sonra yenidən bütün otellərdən keçərək (mümkün olan fərqli bir qaydada) və nəhayət qərargaha qayıdan bir marşrut tapmalıyıq. Turistlərin heç birinin (xüsusilə də sizin) otellərin iki tam turuna məcbur edilməməsini təmin etmək üçün cazibədar yerə gedərkən ilk h/2 otel arasında ziyarət edilən hər bir otel geri qayıdarkən də ilk h/2 otel arasında ziyarət edilməlidir. Bu məhdudiyyətlərə əsasən, tam avtobus turunu mümkün qədər qısa etmək istəyirik. Qeyd edək ki, bu məhdudiyyətlər avtobusun bir otelin yanından keçərək orada dayanmadan keçməsini və sonra onu daha sonra ziyarət etməsini tələb edə bilər, bu, birinci nümunə girişində göstərildiyi kimi ziyarət sayılmır.
Hər test halının ilk sətri n və m tam ədədlərindən ibarətdir və 3 ≤ n ≤ 20 və 2 ≤ m şərtlərini ödəyir, burada n yerlərin (otellər, qərargah, cazibədar yer) sayı və m avtobusun səyahət edə biləcəyi yerlər cütlərinin sayıdır.
n fərqli yerlər 0 ilə n-1 arasında nömrələnmişdir, burada 0 qərargah, 1 ilə n-2 arasında otellər və n-1 cazibədar yerdir. Hər hansı iki yer arasında ən çox birbaşa əlaqənin olduğunu və hər hansı bir yerdən digərinə səyahət etməyin mümkün olduğunu (amma mütləq birbaşa deyil) fərz edin.
Birinci sətirdən sonra m sətir gəlir, hər biri üç tam ədəd u, v və t ehtiva edir ki, burada 0 ≤ u, v ≤ n-1, u ≠ v, 1 ≤ t ≤ 3600, bu da avtobusun u və v yerləri arasında birbaşa t saniyədə hərəkət edə biləcəyini göstərir (hər iki istiqamətdə).
Hər test halı üçün hal nömrəsini və mümkün olan ən qısa turun vaxtını saniyə ilə göstərin.
Nümunə 1