Təcili çatdırılma
Mik və Con - Təcili Çatdırılma işçiləridir. Bir gün onlardan bütün şəhər boyu çoxlu paketləri çatdırmaq xahiş edildi.
Onların işlədiyi şəhərin nəqliyyat sistemi kəsişmələrdən və bu kəsişmələri birləşdirən yollardan ibarətdir. Bütün yollar ikitərəfli və bütün kəsişmələr bir-biri ilə bağlıdır (birbaşa və ya dolayı yolla).
Mik və Con bütün kəsişmələri ziyarət etməli və bütün paketləri çatdırmalıdırlar. Onlar bu vəzifəni iki hissəyə bölmək istəyirlər ki, son çatdırılma vaxtını minimallaşdırsınlar.
Giriş verilənləri
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 18) və m - kəsişmələrin və yolların sayını ehtiva edir.
Növbəti m sətir yolları təsvir edir. Hər sətir üç tam ədəd ehtiva edir: x_i və y_i (1 ≤ x_i, y_i ≤ n) - yolla birləşdirilən kəsişmələrin nömrələri və t_i (1 ≤ t_i ≤ 1000) - bu yolla keçid vaxtı. İki kəsişmə arasında bir yoldan çox yol yoxdur. Heç bir yol kəsişməni öz-özünə birləşdirmir.
Təcili Çatdırılma ofisi 1 nömrəli kəsişmədə yerləşir.
Çıxış verilənləri
Birinci sətirdə son paketin çatdırılma vaxtının minimal mümkün dəyəri göstərilməlidir.
İkinci sətirdə Mik'in yolu göstərilməlidir: Mik tərəfindən keçilən yolların sayı p və ziyarət edilən kəsişmələrin nömrələri p + 1 ardıcıllıqla, 1 nömrəli kəsişmədən başlayaraq.
Üçüncü sətirdə Con'un yolu eyni formatda göstərilməlidir.