Təcili çatdırılma#2378
Mike və John Təcili Çatdırılma üçün işləyirlər. Bir gün onlardan bütün şəhər üzrə çoxlu bağlamalar çatdırmaları xahiş olundu.
Şəhərin nəqliyyat sistemi mötəzimələrdən və onları birləşdirən yollardan ibarətdir. Bütün yollar ikitərəflidir və istənilən mötəziməyə digərindən (birbaşa və ya dolayısı ilə) çatmaq mümkündür.
Mike və John bütün mötəzimələri ziyarət etməlidirlər ki, bütün bağlamalar çatdırılsın. Onlar işi iki hissəyə bölmək istəyirlər ki, sonuncu bağlamanın çatdırılma vaxtı minimum olsun.
Birinci sətirdə iki tam ədəd (1 \le n \le 18) və verilir — mötəzimələrin və yolların sayı.
Növbəti sətrin hər birində bir yolu təsvir edən üç tam ədəd: x_i və y_i (1 \le x_i, y_i \le n) — əlaqəli mötəzimələr, və t_i (1 \le t_i \le 1000) — həmin yol üçün keçid vaxtı. Heç bir iki mötəzimə bir yolla birləşdirilməyib. Heç bir yol bir mötəziməni özü ilə birləşdirmir.
Təcili Çatdırılmanın ofisi -ci mötəzimədə yerləşir.
Birinci sətirdə sonuncu bağlamanın çatdırıldığı minimal mümkün zaman çıxarılmalıdır.
İkinci sətirdə Mike üçün marşrut: Mike tərəfindən keçilən yolların sayı , və onun keçdiyi p + 1 mötəzimənin nömrələri ardıcıllıqla, -ci mötəzimədən başlayaraq.
Üçüncü sətirdə John-un marşrutu eyni formatda olmalıdır.
Nümunə 1