Delta Kvadrant#6964
Delta Kvadrantının böyük bir hissəsi hələ də tədqiq olunmamışdır, lakin məlumdur ki, düşmən irqlərlə məskunlaşmış bir çox təhlükəli bölgələr mövcuddur. Buna baxmayaraq, planetlər arasında təhlükəsiz səyahət edilə bilən bir neçə elan edilmiş neytral zonalar mövcuddur.
Kritik bir sammit planlaşdırılır, lakin bu yalnız üzvlərindən kvorum əldə edildikdə baş tutacaq. Bu kvoruma nail olmaq üçün Delta Kvadrantından demək olar ki, bütün nümayəndələr bir yerə çatdırılmalıdır, oradan isə Enterprise onları sammitə aparacaq.
Enterprise Delta Kvadrantına doğru yoldadır. Siz bir gəmi ilə Delta Kvadrantının bir planetindən başlayaraq həmin planetə qayıtmaqla, müəyyən edilmiş planetlərdən başqa bütün planetləri ziyarət etməyin ən sürətli yolunu tapmalısınız.
n planet və neytral zonalardan keçən n - 1 təhlükəsiz yol mövcuddur, planetləri birləşdirir. Hər yolun keçid vaxtı məlumdur. İstənilən planetdən başlayaraq n - k planetləri ziyarət edib geri qayıtmaq üçün ən az vaxtı tapın.
Birinci sətir testlərin sayını t (1 ≤ t ≤ 50) göstərir. Hər test iki ədəd olan sətirlə başlayır: planetlərin sayı n (2 ≤ n ≤ 10000) və ziyarət edilməməli olan planetlərin sayı k (0 ≤ k ≤ min(n - 1, 20)). Növbəti n - 1 sətirdən hər biri üç tam ədəd ehtiva edir - başlanğıc və son planetlər ( 0 ilə n - 1 arasında) və yolun keçid vaxtı. Vaxt 0 ilə 1000000 arasında daxil olmaqla dəyişir. Giriş qrafı əlaqəlidir.
Hər test üçün ayrıca sətirdə səyahətin ən az vaxtını göstərin.
Nümunə 1