Автобусний тур
Уявіть, що ви турист у Варшаві і забронювали автобусний тур, щоб відвідати захоплюючу пам'ятку за містом. Спочатку автобус їздить містом деякий час (довго, адже Варшава - велике місто), підбираючи пасажирів у їхніх готелях. Потім він прямує до пам'ятки, а через кілька годин повертається в місто, знову заїжджаючи до кожного готелю, цього разу, щоб висадити пасажирів.
З якоїсь причини ваш готель завжди перший для підбору і останній для висадки, що означає, що вам доводиться терпіти два не дуже захоплюючі екскурсійні тури по всіх місцевих готелях. Це явно не те, що ви хочете робити (якщо тільки з якоїсь причини ви дійсно не захоплюєтеся готелями), тому давайте це виправимо. Ми розробимо програмне забезпечення, яке дозволить екскурсійній компанії справедливіше маршрутизувати свої автобусні тури — хоча це іноді може означати довшу загальну відстань для всіх, але справедливість є справедливістю, чи не так?
У цій задачі є початкова локація (штаб-квартира екскурсійної компанії), h готелів, які потрібно відвідати для підбору та висадки, і місце призначення (дивовижна пам'ятка). Нам потрібно знайти маршрут, який починається від штаб-квартири, проходить через усі готелі до пам'ятки, потім повертається через усі готелі знову (можливо, в іншому порядку), і нарешті повертається до штаб-квартири. Щоб гарантувати, що жоден з туристів (і, зокрема, ви) не змушений терпіти два повних тури по готелях, ми вимагаємо, щоб кожен готель, який відвідується серед перших h/2 готелів на шляху до пам'ятки, також відвідувався серед перших h/2 готелів на зворотному шляху. З урахуванням цих обмежень, ми хотіли б зробити повний автобусний тур якомога коротшим. Зверніть увагу, що ці обмеження можуть змусити автобус проїхати повз готель, не зупиняючись там (це не вважається відвідуванням), а потім відвідати його пізніше, як показано в першому прикладі вхідних даних.
Вхідні дані
Перша строка кожного тестового випадку складається з двох цілих чисел n та m, що задовольняють 3 ≤ n ≤ 20 та 2 ≤ m, де n - це кількість локацій (готелі, штаб-квартира, пам'ятка), а m - це кількість пар локацій, між якими автобус може подорожувати.
n різних локацій пронумеровані від 0 до n-1, де 0 - це штаб-квартира, 1 до n-2 - це готелі, а n-1 - це пам'ятка. Припустимо, що існує не більше одного прямого з'єднання між будь-якою парою локацій і можливо подорожувати від будь-якої локації до будь-якої іншої (але не обов'язково безпосередньо).
Після першої строки йдуть m рядків, кожен з яких містить три цілі числа u, v та t такі, що 0 ≤ u, v ≤ n-1, u ≠ v, 1 ≤ t ≤ 3600, що вказує, що автобус може їхати безпосередньо між локаціями u та v за t секунд (в обох напрямках).
Вихідні дані
Для кожного тестового випадку виведіть номер випадку та час у секундах найкоротшого можливого туру.